Round-Efficient Distributed Byzantine Computation
share
We present the first round efficient algorithms for several fundamental distributed tasks in the presence of a Byzantine edge. Our algorithms work in the CONGEST model of distributed computing. In the Byzantine Broadcast problem, given is a network G=(V,E) with an unknown Byzantine edge e'. There is a source node s holding an initial message m_0, and the goal is for all the nodes in the network to receive a copy of m_0, while ignoring all other messages. Perhaps surprisingly, to the best of our knowledge, all existing algorithms for the problem either assume that the Byzantine behavior is probabilistic, use polynomially large messages or else suffer from a large round complexity. We give an O(D^2)-round [%s] algorithm for the Byzantine Broadcast problem, where D is the diameter of the graph. The communication graph is required to be 3-edge connected, which is known to be a necessary condition. We also provide a Leader Election algorithm in the presence of a Byzantine edge with the same round complexity of O(D^2) rounds. We use these algorithms to provide the efficient construction of Byzantine cycle covers which serve the basis for (i) Byzantine BFS algorithms and (ii) a general compiler for algorithms in the presence of a Byzantine edge. We hope that the tools provided in this paper will pave the way towards obtaining round-efficient algorithms for many more distributed problems in the presence of Byzantine edges and nodes.
READ FULL TEXT