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

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).

Link to Full Text

Share

COinS