Computer Science

Fault-tolerant consensus in directed graphs

Document Type

Conference Paper

Abstract

Consider a point-to-point network in which nodes are connected by directed links. This paper proves tight necessary and sufficient conditions on the underlying communication graphs for solving the following fault-tolerant consensus problems: Exact crash-tolerant consensus in synchronous systems, Approximate crash-tolerant consensus in asynchronous systems, and Exact Byzantine consensus in synchronous systems. The problem of asynchronous Byzantine consensus in directed graphs remains open. Prior work has developed analogous necessary and sufficient conditions for undirected graphs [11, 3, 9]. However, the conditions for undirected graphs are not adequate to completely characterize these consensus problems in directed graphs. Moreover, the algorithms for directed graphs presented in this paper are substantially different from those previously developed for undirected graphs. Other prior work on directed graphs has explored somewhat different problems than those solved in this paper.

Publication Title

Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Publication Date

2015

Volume

2015-July

First Page

451

Last Page

460

ISBN

9781450336178

DOI

10.1145/2767386.2767399

Keywords

asynchronous and synchronous systems, consensus, crash and byzantine faults, directed networks

APA Citation

Tseng, L., & Vaidya, N. H. (2015, July). Fault-tolerant consensus in directed graphs. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (pp. 451-460).

Link to Full Text

Share

COinS