Impossibility of Distributed Consensus with One Faulty Process
📜 Abstract
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.
✨ Summary
Main contribution
The paper proves the FLP impossibility result: no deterministic consensus protocol can guarantee termination in a completely asynchronous message-passing system if even one process may fail by stopping, despite reliable message delivery and otherwise strong computational assumptions. The result applies to a weak consensus specification requiring agreement, the possibility of both decision values, and eventual decision by at least one process.
The proof first establishes the existence of a bivalent initial configuration, from which both decision values remain possible. It then shows that, from any bivalent configuration, the scheduler can choose a finite sequence of process events that preserves bivalence while still allowing any selected next event to occur last. By repeatedly extending the execution in this way, the authors construct an admissible infinite run in which every process continues taking steps and messages to nonfaulty processes are eventually delivered, yet no process ever decides. Thus, safety can be maintained, but guaranteed termination cannot.
The paper also gives a contrasting protocol for the case where a strict majority of processes are initially alive and no process fails during execution. This illustrates that the impossibility depends specifically on the combination of asynchronous timing and an execution-time crash, rather than on consensus agreement alone.
Influence
The result directly motivated subsequent approaches that weaken the model or modify the problem. Ben-Or explicitly used the FLP impossibility result as motivation for a randomized, completely asynchronous consensus protocol that terminates with probability 1 when a majority of processes continue operating. (homepage.cs.uiowa.edu) Dwork, Lynch, and Stockmeyer developed partially synchronous models and consensus protocols that recover termination guarantees under eventual timing bounds, explicitly addressing the limitation exposed by FLP. (groups.csail.mit.edu) Chandra and Toueg introduced unreliable failure detectors as an abstraction for solving consensus in asynchronous systems with crash failures, providing another way to add the information absent from the FLP model. (cs.princeton.edu)
The paper received the 2001 PODC Influential Paper Award. The award citation identifies its influence on partially synchronous systems, failure detectors, randomized algorithms, approximate agreement, k-set consensus, renaming, valency-based lower bounds, and the wait-free hierarchy. (podc.org)