Iterative approximate byzantine consensus in arbitrary directed graphs

Nitin H Vaidya, Lewis Tseng, Guanfeng Liang

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

Abstract

This paper proves a necessary and sufficient condition for the existence of iterative, algorithms that achieve approximate Byzantine consensus in arbitrary directed graphs, where each directed edge represents a communication channel between a pair of nodes. The class of iterative algorithms considered in this paper ensures that, after each iteration of the algorithm, the state of each fault-free node remains in the convex hull of the states of the fault-free nodes at the end of the previous iteration. The following convergence requirement is imposed: for any ε > 0, after a sufficiently large number of iterations, the states of the fault-free nodes are guaranteed to be within ε of each other. To the best of our knowledge, tight necessary and sufficient conditions for the existence of such iterative consensus algorithms in synchronous arbitrary point-to-point networks in presence of Byzantine faults, have not been developed previously. The methodology and results presented in this paper can also be extended to asynchronous systems.

Original languageEnglish (US)
Title of host publicationPODC'12 - Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing
Pages365-374
Number of pages10
DOIs
StatePublished - Aug 20 2012
Event2012 ACM Symposium on Principles of Distributed Computing, PODC'12 - Madeira, Portugal
Duration: Jul 16 2012Jul 18 2012

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other2012 ACM Symposium on Principles of Distributed Computing, PODC'12
CountryPortugal
CityMadeira
Period7/16/127/18/12

Keywords

  • byzantine faults
  • consensus
  • iterative algorithms

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Iterative approximate byzantine consensus in arbitrary directed graphs'. Together they form a unique fingerprint.

  • Cite this

    Vaidya, N. H., Tseng, L., & Liang, G. (2012). Iterative approximate byzantine consensus in arbitrary directed graphs. In PODC'12 - Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (pp. 365-374). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). https://doi.org/10.1145/2332432.2332505