Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms

This paper addresses the problem of distributed multi-agent optimization in which each agent i has a local cost function hi(x), and the goal is to optimize a global cost function that aggregates the local cost functions. Such optimization problems are of interest in many contexts, including distributed machine learning, distributed resource allocation, and distributed robotics. We consider the distributed optimization problem in the presence of faulty agents. We focus primarily on Byzantine failures, but also briey discuss some results for crash failures. For the Byzantine fault-tolerant optimization problem, the ideal goal is to optimize the average of local cost functions of the non-faulty agents. However, this goal also cannot be achieved. Therefore, we consider a relaxed version of the fault-tolerant optimization problem. The goal for the relaxed problem is to generate an output that is an optimum of a global cost function formed as a convex combination of local cost functions of the non-faulty agents. More precisely, there must exist weights ai for iN such that ai 0 and i Nai=1, and the output is an optimum of the cost function i N aihi(x). Ideally, we would like ai=1/textbarNtextbar for all i N, however, this cannot be guaranteed due to the presence of faulty agents. In fact, the maximum number of nonzero weights (ai's) that can be guaranteed is textbarNtextbar-f, where f is the maximum number of Byzantine faulty agents. We present an iterative distributed algorithm that achieves optimal fault-tolerance. Specifically, it ensures that at least textbarNtextbar-f agents have weights that are bounded away from 0 (in particular, lower bounded by 1/2textbarNtextbar-f\vphantom\\). The proposed distributed algorithm has a simple iterative structure, with each agent maintaining only a small amount of local state. We show that the iterative algorithm ensures two properties as time goes to : consensus (i.e., output of non-faulty agents becomes identical in the time limit), and optimality (in the sense that the output is the optimum of a suitably defined global cost function).