Error-Free Multi-Valued Consensus with Byzantine Failures
Abstract
In this paper, we present an efficient deterministic algorithm for consensus in presence of Byzantine failures. Our algorithm achieves consensus on an L-bit value with communication complexity O(nL + n4L0.5 + n6) bits, in a network consisting of n processors with up to t Byzantine failures, such that t < n/3. For large enough L, communication complexity of the proposed algorithm approaches O(nL) bits. In other words, for large L, the communication complexity is linear in the number of processors in the network. This is an improvement over the work of Fitzi and Hirt (from PODC 2006), who proposed a probabilistically correct multivalued Byzantine consensus algorithm with a similar complexity for large L. In contrast to the algorithm by Fitzi and Hirt, our algorithm is guaranteed to be always error-free. Our algorithm require no cryptographic technique, such as authentication, nor any secret sharing mechanism. To the best of our knowledge, we are the first to show that, for large L, error-free multi-valued Byzantine consensus on an L-bit value is achievable with O(nL) bits of communication.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 19, 2011
- Accession Number
- ADA555083
Entities
People
- Guanfeng Liang
- Nitin H. Vaidya
Organizations
- University of Illinois Urbana–Champaign