Fault-Tolerant Consensus in Directed Graphs
Lewis Tseng, Nitin H. Vaidya · 2015
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.