We study the problem of constrained distributed optimization in multi-agent networks when some of the computing agents may be faulty. In this problem, the system goal is to have all the non-faulty agents collectively minimize a global objective given by weighted average of local cost functions, each of which is initially known to a non-faulty agent only. In particular, we are interested in the scenario when the computing agents are connected by an arbitrary directed communication network, some of the agents may suffer from crash faults or Byzantine faults, and the estimate of each agent is restricted to lie in a common constraint set. This problem finds its applications in social computing and distributed large-scale machine learning. The fault-tolerant multi-agent optimization problem was first formulated by Su and Vaidya, and is solved when the local functions are defined over the whole real line, and the networks are fully-connected. In this report, we consider arbitrary directed communication networks and focus on the scenario where, local estimates at the non-faulty agents are constrained, and only local communication and minimal memory carried across iterations are allowed. In particular, we generalize our previous results on fully-connected networks and unconstrained optimization to arbitrary directed networks and constrained optimization. As a byproduct, we provide a matrix representation for iterative approximate crash consensus. The matrix representation allows us to characterize the convergence rate for crash iterative consensus.
Fault-tolerant consensus @cite_24 is a special case of the optimization problem considered in this report. There is a significant body of work on fault-tolerant consensus, including @cite_32 @cite_27 @cite_5 @cite_14 @cite_15 @cite_10 . The optimization algorithms presented in this report use fault-tolerant consensus as a component.
@cite_14 @cite_32 @cite_24 @cite_27 @cite_5 @cite_15 @cite_10
1760770890 2147056869 1510375514 2025713377
This work addresses Byzantine vector consensus, wherein the input at each process is a d-dimensional vector of reals, and each process is required to decide on a decision vector that is in the convex hull of the input vectors at the fault-free processes [9,12]. The input vector at each process may also be viewed as a point in the d-dimensional Euclidean space R d , where di¾?>i¾?0 is a finite integer. Recent work [9,12] has addressed Byzantine vector consensus, and presented algorithms with optimal fault tolerance in complete graphs. This paper considers Byzantine vector consensus in incomplete graphs using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations. For such algorithms, we prove a necessary condition, and a sufficient condition, for the graphs to be able to solve the vector consensus problem iteratively. We present an iterative Byzantine vector consensus algorithm, and prove it correct under the sufficient condition. The necessary condition presented in this paper for vector consensus does not match with the sufficient condition for di¾?>i¾?1; thus, a weaker condition may potentially suffice for Byzantine vector consensus. Much of the past work on asynchronous approximate Byzantine consensus has assumed scalar inputs at the nodes [4, 8]. Recent work has yielded approximate Byzantine consensus algorithms for the case when the input at each node is a d-dimensional vector, and the nodes must reach consensus on a vector in the convex hull of the input vectors at the fault-free nodes [9, 13]. The d-dimensional vectors can be equivalently viewed as points in the d-dimensional Euclidean space. Thus, the algorithms in [9, 13] require the fault-free nodes to decide on a point in the d-dimensional space. In our recent work [12], we proposed a generalization of the consensus problem, namely Byzantine convex consensus (BCC), which allows the decision to be a convex polytope in the d-dimensional space, such that the decided polytope is within the convex hull of the input vectors at the fault-free nodes. We also presented an asynchronous approximate BCC algorithm. In this paper, we propose a new BCC algorithm with optimal fault-tolerance that also agrees on a convex polytope that is as large as possible under adversarial conditions. Our prior work [12] does not guarantee the optimality of the output polytope. In this work, we consider a generalized fault model [7,9,5] that can be used to represent a wide range of failure scenarios, including correlated failures and non-uniform node reliabilities. Under the generalized fault model, we explore iterative approximate Byzantine consensus (IABC) algorithms [15] in arbitrary directed networks. We prove a tight necessary and sufficient condition on the underlying communication graph for the existence of IABC algorithms. The consensus problem is at the heart of solutions related to the development of modern reliable distributed systems. This paper studies necessary and sufficient conditions under which fault-tolerant consensus become solvable in dynamic systems and self-organizing networks. Those conditions are related to the synchrony requirements of the environment, to the connectivity of the knowledge graph constructed by the nodes in order to communicate with their peers, as well as to the knowledge about global parameters in the system, such as, the total number of participants and the maximum number of node crashes.