### 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 language | English (US) |
---|---|

Title of host publication | 2016 American Control Conference, ACC 2016 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 7183-7188 |

Number of pages | 6 |

ISBN (Electronic) | 9781467386821 |

DOIs | |

State | Published - Jul 28 2016 |

Event | 2016 American Control Conference, ACC 2016 - Boston, United States Duration: Jul 6 2016 → Jul 8 2016 |

### Publication series

Name | Proceedings of the American Control Conference |
---|---|

Volume | 2016-July |

ISSN (Print) | 0743-1619 |

### Other

Other | 2016 American Control Conference, ACC 2016 |
---|---|

Country | United States |

City | Boston |

Period | 7/6/16 → 7/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

*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