Capacity of Byzantine Agreement: Complete Characterization of Four-Node Networks

摘要

In this paper, we consider the problem of maximizing the throughput of Byzantine agreement. Byzantine agreement is a classical problem in distributed computing, with initial solutions presented in the seminal work of Pease, Shostak and Lamport. Many variations on the Byzantine agreement problem have been introduced in the past, with some of the variations also called consensus. We will use the following definition of Byzantine agreement: Consider a network with one node designated as the sender or source (S), and the other nodes designated as the peers. The goal of Byzantine agreement is for all the fault-free nodes to 'agree on' the value being sent by the sender, despite the possibility that some of the nodes may be faulty. In particular, the following conditions must be satisfied: * Agreement: All fault-free peers must agree on an identical value. * Validity: If the sender is fault-free, then the agreed value must be identical to the sender's value. * Termination: Agreement between fault-free peers is eventually achieved. Our goal in this work is to design algorithms that can achieve optimal throughput of agreement. When defining throughput, the 'value' referred in the above definition of agreement is viewed as an infinite sequence of bits. At each peer, we view the agreed information as being represented in an array of infinite length. Initially, none of the bits in this array at a peer have been agreed upon. As time progresses, the array is filled in with agreed bits. In principle, the array may not necessarily be filled sequentially. For instance, a peer may agree on bit number 3 before it is able to agree on bit number 2. Once a peer agrees on any bit, that agreed bit cannot be changed.