Byzantine Multi-Agent Optimization: Part I

Author name not available (Why is that?)

Publication date: 15 June 2015

Abstract: We study Byzantine fault-tolerant distributed optimization of a sum of convex (cost) functions with real-valued scalar input/ouput. In particular, the goal is to optimize a global cost function

f r a c 1 | m a t h c a l N | s u m_{i i n m a t h c a l N} h_{i} (x)

, where

m a t h c a l N

is the set of non-faulty agents, and

h_{i} (x)

is agent

i

's local cost function, which is initially known only to agent

i

. In general, when some of the agents may be Byzantine faulty, the above goal is unachievable, because the identity of the faulty agents is not necessarily known to the non-faulty agents, and the faulty agents may behave arbitrarily. Since the above global cost function cannot be optimized exactly in presence of Byzantine agents, we define a weaker version of the problem. The goal for the weaker problem is to generate an output that is an optimum of a function formed as a convex combination of local cost functions of the non-faulty agents. More precisely, for some choice of weights

a l p h a_{i}

for

i i n m a t h c a l N

such that

a l p h a_{i} g e q 0

and

s u m_{i i n m a t h c a l N} a l p h a_{i} = 1

, the output must be an optimum of the cost function

s u m_{i i n m a t h c a l N} a l p h a_{i} h_{i} (x)

. Ideally, we would like

a l p h a_{i} = f r a c 1 | m a t h c a l N |

for all

i i n m a t h c a l N

-- however, this cannot be guaranteed due to the presence of faulty agents. In fact, we show that the maximum achievable number of nonzero weights (

a l p h a_{i}

's) is

| m a t h c a l N | - f

, where

f

is the upper bound on the number of Byzantine agents. In addition, we present algorithms that ensure that at least

| m a t h c a l N | - f

agents have weights that are bounded away from 0. We also propose a low-complexity suboptimal algorithm, which ensures that at least

l c e i l f r a c n 2 c e i l - p h i

agents have weights that are bounded away from 0, where

n

is the total number of agents, and

p h i

(

p h i l e f

) is the actual number of Byzantine agents.

Has companion code repository: https://github.com/kkuwaran/resilient-distributed-optimization

This page was built for publication: Byzantine Multi-Agent Optimization: Part I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6262700)