TY - GEN

T1 - Multi-agent optimization in the presence of Byzantine adversaries

T2 - 2016 American Control Conference, ACC 2016

AU - Su, Lili

AU - Vaidya, Nitin

PY - 2016/7/28

Y1 - 2016/7/28

N2 - We study multi-agent optimization problem in the presence of Byzantine adversaries, where each agent i has a local cost function hi(x), and some unknown subset of agents suffer Byzantine faults. The goal is to optimize a global objective that properly aggregates the local cost functions. Ideally, we would like to optimize 1 over |N| Σi?N hi(x), where N is the set of non-faulty agents. However, we show that this ideal goal is unachievable. Therefore, we define a relaxed version of the problem, named Byzantine multi-agent optimization, for which the goal is to generate an output that is an optimum of a global cost function formed as a convex combination of local cost functions kept by the non-faulty agents. More precisely, there must exist nonnegative weights αi for i ? N such that Σi?N αi = 1, and the output is an optimum of Σi?N αihi(x). In this paper, we focus on the impact of Byzantine attacks on the maximal achievable number of nonzero weights. To characterize the fundamental limits, we assume that the argument of each local cost function is a (real-valued) scalar, the network is fully-connected, and there is no restriction on the information exchange among agents. We show that the number of nonzero weights (αi's) that can be guaranteed is at most |N| - f, where f is the maximum number of Byzantine faulty agents. Additionally, we present algorithms that achieve this upper bound. By exploiting Byzantine broadcast for information exchange between agents, our proposed algorithms essentially solve a centralized problem where there are n functions among which up to f functions are injected by the system adversary.

AB - We study multi-agent optimization problem in the presence of Byzantine adversaries, where each agent i has a local cost function hi(x), and some unknown subset of agents suffer Byzantine faults. The goal is to optimize a global objective that properly aggregates the local cost functions. Ideally, we would like to optimize 1 over |N| Σi?N hi(x), where N is the set of non-faulty agents. However, we show that this ideal goal is unachievable. Therefore, we define a relaxed version of the problem, named Byzantine multi-agent optimization, for which the goal is to generate an output that is an optimum of a global cost function formed as a convex combination of local cost functions kept by the non-faulty agents. More precisely, there must exist nonnegative weights αi for i ? N such that Σi?N αi = 1, and the output is an optimum of Σi?N αihi(x). In this paper, we focus on the impact of Byzantine attacks on the maximal achievable number of nonzero weights. To characterize the fundamental limits, we assume that the argument of each local cost function is a (real-valued) scalar, the network is fully-connected, and there is no restriction on the information exchange among agents. We show that the number of nonzero weights (αi's) that can be guaranteed is at most |N| - f, where f is the maximum number of Byzantine faulty agents. Additionally, we present algorithms that achieve this upper bound. By exploiting Byzantine broadcast for information exchange between agents, our proposed algorithms essentially solve a centralized problem where there are n functions among which up to f functions are injected by the system adversary.

UR - http://www.scopus.com/inward/record.url?scp=84992163568&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84992163568&partnerID=8YFLogxK

U2 - 10.1109/ACC.2016.7526806

DO - 10.1109/ACC.2016.7526806

M3 - Conference contribution

AN - SCOPUS:84992163568

T3 - Proceedings of the American Control Conference

SP - 7183

EP - 7188

BT - 2016 American Control Conference, ACC 2016

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 6 July 2016 through 8 July 2016

ER -