Capacity of Byzantine Consensus with Capacity-Limited Point-to-Point Links

摘要

In our previous work 5, 4, and 6, we investigated the capacity of the broadcast version of the Byzantine agreement problem 3) in networks where communications links are capacity limited. In this report, we are going to study capacity of the consensus version of the Byzantine agreement problem. The Byzantine consensus problem considers n nodes, namely P1, ..., Pn, of which at most f nodes may be faulty and deviate from the algorithm in arbitrary fashion. Each node Pi is given an input value vi, and they want to agree on a value v such that the following properties are satisfied: Termination: every fault-free Pi eventually decides on an output value v i , Consistency: the output values of all fault-free nodes are equal, i.e., for every fault-free node Pi, v i = v for some v , Validity: if every fault-free Pi holds the same input vi = v for some v, then v = v.