Fully-Distributed Byzantine Agreement in Sparse Networks

Byzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protocols for complete networks. A key goal in Byzantine protocols is to tolerate as many Byzantine nodes as possible.

The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was the first to address the Byzantine agreement problem in sparse, bounded degree networks and presented a protocol that achieved almost-everywhere agreement among honest nodes. In such networks, all known Byzantine agreement protocols (e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King, Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine nodes had a major drawback that they were not fully-distributed -in those protocols, nodes are required to have initial knowledge of the entire network topology. This drawback makes such protocols inapplicable to real-world communication networks such as peer-to-peer (P2P) networks, which are typically sparse and bounded degree and where nodes initially have only local knowledge of themselves and their neighbors. Indeed, a fundamental open question raised by the above works is whether one can design Byzantine protocols that tolerate a large number of Byzantine nodes in sparse networks that work with only local knowledge, i.e., fully-distributed protocols. The work of Augustine, Pandurangan, and Robinson [PODC 2013] presented the first fully-distributed Byzantine agreement protocol that works in sparse networks, but it tolerated only up to O( √ n/ polylog n) Byzantine nodes (where n is the total network size).

We present fully-distributed Byzantine agreement protocols for sparse, bounded degree networks that tolerate significantly more Byzantine nodes, answering the earlier open question. Our protocols work under the powerful full information model where the Byzantine nodes can behave arbitrarily and maliciously, have knowledge about the entire state of the network at every round, including random choices made by the nodes up to (and including) the current round, have unlimited computational power, and may collude among themselves. We first present a protocol that tolerates up to o( n log n ) Byzantine nodes and with high probability 1 , solves almost-everywhere agreement where all except o(n) honest nodes reach agreement. The protocol runs in Õ(n 2 ) rounds. We then present a faster protocol that runs in nearly linear (i.e., Õ(n)) rounds and tolerates up to o( n log 2 n ) Byzantine nodes. Both protocols are communication-efficient in the sense that honest nodes send only polylog n bits per edge per round.