Multi-agent optimization in the presence of Byzantine adversaries: Fundamental limits

Lili Su, Nitin Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2016 American Control Conference, ACC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages7183-7188
Number of pages6
ISBN (Electronic)9781467386821
DOIs
StatePublished - Jul 28 2016
Event2016 American Control Conference, ACC 2016 - Boston, United States
Duration: Jul 6 2016Jul 8 2016

Publication series

NameProceedings of the American Control Conference
Volume2016-July
ISSN (Print)0743-1619

Other

Other2016 American Control Conference, ACC 2016
CountryUnited States
CityBoston
Period7/6/167/8/16

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Multi-agent optimization in the presence of Byzantine adversaries: Fundamental limits'. Together they form a unique fingerprint.

  • Cite this

    Su, L., & Vaidya, N. (2016). Multi-agent optimization in the presence of Byzantine adversaries: Fundamental limits. In 2016 American Control Conference, ACC 2016 (pp. 7183-7188). [7526806] (Proceedings of the American Control Conference; Vol. 2016-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ACC.2016.7526806