Computer Science

Iterative approximate byzantine consensus in arbitrary directed graphs

Document Type

Conference Paper

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. © 2012 ACM.

Publication Title

Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Publication Date

2012

First Page

365

Last Page

374

ISBN

9781450314503

DOI

10.1145/2332432.2332505

Keywords

byzantine faults, consensus, iterative algorithms

APA Citation

Vaidya, N. H., Tseng, L., & Liang, G. (2012, July). Iterative approximate Byzantine consensus in arbitrary directed graphs. In Proceedings of the 2012 ACM symposium on Principles of distributed computing (pp. 365-374).

Link to Full Text

Share

COinS