Capacity of Byzantine Consensus with Capacity-Limited Point-to-Point Links
Abstract
In our previous work [5, 4, 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 31, 2011
- Accession Number
- ADA555091
Entities
People
- Guanfeng Liang
- Nitin H. Vaidya
Organizations
- University of Illinois Urbana–Champaign