Computer Science
Asynchronous Byzantine Approximate Consensus in Directed Networks
Document Type
Conference Paper
Abstract
This paper considers the problem of approximate consensus in directed asynchronous message-passing networks where some nodes may become Byzantine faulty. We obtain a tight necessary and sufficient condition on the underlying directed communication network for asynchronous Byzantine approximate consensus to be achievable. Interestingly, this condition coincides with the tight condition for synchronous Byzantine exact consensus. Our consensus algorithm may be viewed as a non-trivial generalization of an algorithm previously proposed for the special case of complete networks. The tight condition and techniques identified in the paper shed light on the fundamental properties for solving approximate consensus in asynchronous directed networks.
Publication Title
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Publication Date
2020
First Page
149
Last Page
158
ISBN
9781450375825
DOI
10.1145/3382734.3405724
Keywords
approximate consensus, asynchronous networks, byzantine adversary, directed networks
Repository Citation
Sakavalas, Dimitris; Tseng, Lewis; and Vaidya, Nitin H., "Asynchronous Byzantine Approximate Consensus in Directed Networks" (2020). Computer Science. 123.
https://commons.clarku.edu/faculty_computer_sciences/123
APA Citation
Sakavalas, D., Tseng, L., & Vaidya, N. H. (2020, July). Asynchronous Byzantine approximate consensus in directed networks. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 149-158).