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.