Error-free multi-valued consensus with byzantine failures

Guanfeng Liang, Nitin Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 + n4L 0.5 + n6) bits, in a network consisting of n processors with up to t Byzantine failures, such that tn/3. For large enough L, communication complexity of the proposed algorithm becomes O(nL) 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 cost can be traded off with the strength of the validity condition. The proposed algorithm requires no cryptographic techniques.

Original languageEnglish (US)
Title of host publicationPODC'11 - Proceedings of the 2011 ACM Symposium Principles of Distributed Computing
Pages11-20
Number of pages10
DOIs
StatePublished - 2011
Event30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC'11, Held as Part of the 5th Federated Computing Research Conference, FCRC - San Jose, CA, United States
Duration: Jun 6 2011Jun 8 2011

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC'11, Held as Part of the 5th Federated Computing Research Conference, FCRC
CountryUnited States
CitySan Jose, CA
Period6/6/116/8/11

Keywords

  • byzantine agreement
  • consensus
  • distributed computing

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Error-free multi-valued consensus with byzantine failures'. Together they form a unique fingerprint.

Cite this