Iterative Approximate Consensus in the presence of Byzantine Link Failures?

Abstract. This paper explores the problem of reaching approximate consensus in synchronous point-to-point networks, where each directed link of the underlying communication graph represents a communication channel between a pair of nodes. We adopt the transient Byzantine link failure model [15,16], where an omniscient adversary controls a subset of the directed communication links, but the nodes are assumed to be fault-free. Recent work has addressed the problem of reaching approximate consen-sus in incomplete graphs with Byzantine nodes using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations [22,21,23,12]. However, to the best of our knowledge, we are the first to consider approximate consensus in the presence of Byzan-tine links. We extend our past work that provided exact characterization of graphs in which the iterative approximate consensus problem in the presence of Byzantine node failures is solvable [22,21]. In particular, we prove a tight necessary and sufficient condition on the underlying com-munication graph for the existence of iterative approximate consensus algorithms under transient Byzantine link model. The condition answers (part of) the open problem stated in [16].