Fault-tolerant consensus in directed graphs

Lewis Tseng, The Grainger College of Engineering
Nitin H. Vaidya, The Grainger College of Engineering

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.