  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). We first characterize certain
fundamental limitations on the performance of any distributed optimization
algorithm in the presence of adversaries. We then propose a resilient
distributed optimization algorithm that guarantees that the non-adversarial
nodes converge to the convex hull of the minimizers of their local functions
under certain conditions on the graph topology, regardless of the actions of a
certain number of adversarial nodes. In particular, we provide sufficient
conditions on the graph topology to tolerate a bounded number of adversaries in
the neighborhood of every non-adversarial node, and necessary and sufficient
conditions to tolerate a globally bounded number of adversaries. For situations
where there are up to F adversaries in the neighborhood of every node, we use
the concept of maximal F-local sets of graphs to provide lower bounds on the
distance-to-optimality of achievable solutions under any algorithm. We show
that finding the size of such sets is NP-hard.
