Iterative approximate Byzantine consensus in arbitrary directed graphs

• Published in: Distributed computing 2024-09, Vol.37 (3), p.225-246
• Main Authors: Tseng, Lewis, Liang, Guanfeng, Vaidya, Nitin H.
• Format: Article
• Language: English
• Subjects: Algorithms; Computer Communication Networks; Computer Hardware; Computer Science; Computer Systems Organization and Communication Networks; Convexity; Evolutionary algorithms; Fault detection; Fault tolerance; Graph theory; Graphs; Iterative algorithms; Nodes; Software Engineering/Programming and Operating Systems; Theory of Computation
• ISSN: 0178-2770; 1432-0452
• DOI: 10.1007/s00446-024-00468-2

This paper identifies necessary and sufficient conditions for the existence of iterative algorithms that achieve approximate Byzantine consensus in arbitrary directed graphs, where each directed link 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. We present the necessary and sufficient condition for the existence of such iterative consensus algorithms in synchronous arbitrary point-to-point networks in presence of Byzantine faults in two different equivalent forms. We prove the necessity using an indistinguishability argument. For sufficiency, we develop a proof framework, which first uses a series of “transition matrices” to model the state evolution of the fault-free nodes using our algorithm, and then proves the correctness by identifying important properties of the matrices. The proof framework is useful for other iterative fault-tolerant algorithms. We discuss the extensions to asynchronous systems and the Byzantine links fault model.