Byzantine Multi-Agent Optimization: Part I

We study Byzantine fault-tolerant distributed optimization of a sum of convex (cost) functions with real-valued scalar input/ouput. In particular, the goal is to optimize a global cost function frac1|N|sumi∈ N hi(x), where N is the set of non-faulty agents, and hi(x) is agent i's local cost function, which is initially known only to agent i. In general, when some of the agents may be Byzantine faulty, the above goal is unachievable, because the identity of the faulty agents is not necessarily known to the non-faulty agents, and the faulty agents may behave arbitrarily. Since the above global cost function cannot be optimized exactly in presence of Byzantine agents, we define a weaker version of the problem. The goal for the weaker problem is to generate an output that is an optimum of a function formed as a convex combination of local cost functions of the non-faulty agents. More precisely, for some choice of weights αi for i∈ N such that αi≥ 0 and sumi∈ Nαi=1, the output must be an optimum of the cost function sumi∈ N αihi(x). Ideally, we would like αi=frac1|N| for all i∈ N -- however, this cannot be guaranteed due to the presence of faulty agents. In fact, we show that the maximum achievable number of nonzero weights (αi's) is |N|-f, where f is the upper bound on the number of Byzantine agents. In addition, we present algorithms that ensure that at least |N|-f agents have weights that are bounded away from 0. We also propose a low-complexity suboptimal algorithm, which ensures that at least lceil fracn2rceil-φ agents have weights that are bounded away from 0, where n is the total number of agents, and φ (φ≤ f) is the actual number of Byzantine agents.