Error-Free Multi-Valued Consensus with Byzantine Failures

摘要

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 + n~4 L~(0.5) + n~6) 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 becomes O(n L) bits, linear in the number of processors. To achieve this goal, the algorithm performs consensus on a long message (L bits), in multiple generations, each generation performing consensus on a part of the input message. The failure-free execution of each generation is made efficient by using a combination of two techniques: error detection coding, and processor clique formation based on matching input values proposed by the processors. By keeping track of faulty behavior over the different generations, the algorithm can ensure that most generations of the algorithm are failure-free. With parameterization, our algorithm is able to achieve a large class of validity conditions for consensus, while maintaining linear communication complexity. With a suitable choice of the error detection code, and using a clique of an appropriate size, the communication cast can be traded off with the strength of the validity condition. The proposed algorithm requires no cryptographic techniques.