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.
We investigate the vulnerabilities of consensus-based distributed optimization protocols to nodes that deviate from the prescribed update rule (e.g., due to failures or adversarial attacks). After characterizing certain fundamental limitations on the performance of any distributed optimization algorithm in the presence of adversaries, we propose a robust consensus-based distributed optimization algorithm that is guaranteed to converge to the convex hull of the set of minimizers of the non-adversarial nodes' functions. We also study the distance-to-optimality properties of our proposed robust algorithm in terms of F-local sets of the graph. We show that finding the largest size of such sets is NP-hard.