Reaching approximate Byzantine consensus with multi-hop communication

We are interested in approximate Byzantine consensus problem, wherein all the fault-free processes reach consensus asymptotically (approximately in finite time). In particular, we focus on the algorithms under which each process communicates with other processes that are up to l hops away and maintains minimal states across iterations. For a given l, we identify a necessary and sufficient condition on the network structure for the existence of iterative algorithms of interest. Our necessary and sufficient condition generalizes the tight condition identified in prior work for l = 1. For l > l*, where l* is the length of a longest cycle-free path in the given network, our condition is equivalent to the necessary and sufficient conditions for exact consensus in undirected and directed networks both. (C) 2016 Elsevier Inc. All rights reserved.