Distributed Consensus

Distributed consensus is the problem of getting a set of processes to agree on a single value despite message delays and process failures, and it is the central abstraction of fault-tolerant computing.

Definition

Consensus requires that each non-faulty process, starting from a proposed input, eventually decides on an output value such that all non-faulty processes decide the same value (agreement), the value was proposed by some process (validity), and every non-faulty process eventually decides (termination).

Scope

This topic covers the formal specification of consensus (agreement, validity, integrity, and termination), the FLP impossibility theorem and the ways it is circumvented—partial synchrony, unreliable failure detectors, and randomization—and the equivalence of consensus with atomic broadcast and replicated state machines. It treats the crash-failure setting; the Byzantine setting is treated in a sibling topic.

Core questions

• What exactly must a protocol guarantee to be a correct consensus algorithm?
• Why is deterministic asynchronous consensus impossible with even one crash?
• Which additional assumptions—synchrony, failure detectors, randomness—restore solvability?

Key theories

FLP impossibility

No deterministic protocol solves consensus in an asynchronous message-passing system if even one process may crash, because every protocol has an execution that can be steered to run forever without deciding.

Failure-detector approach

Augmenting an asynchronous system with an unreliable failure detector that is eventually accurate restores the solvability of consensus, and the weakest such detector that suffices has been precisely characterized.

Randomized consensus

Allowing processes to flip coins lets consensus terminate with probability one even in a fully asynchronous system, trading deterministic termination for probabilistic termination to escape the FLP barrier.

Clinical relevance

Every strongly consistent distributed system—replicated logs, coordination services, configuration stores—solves consensus internally, so the guarantees and limits established here directly bound what such systems can promise about consistency and availability.

History

The 1985 FLP theorem established the fundamental impossibility; Ben-Or's 1983 randomized protocol and Chandra and Toueg's 1996 failure-detector framework then showed two complementary ways to make consensus solvable, defining the research agenda for the following decades.

Key figures

• Michael Fischer
• Nancy Lynch
• Michael Paterson
• Tushar Chandra
• Sam Toueg
• Michael Ben-Or

Seminal works

• fischer1985
• chandra1996
• ben-or1983

Frequently asked questions

If consensus is impossible, how do real systems achieve it?

The impossibility applies only to a deterministic protocol that must always terminate in a fully asynchronous model. Real systems keep safety unconditional and rely on eventual synchrony or randomness for termination, so they never violate agreement and make progress whenever the network is well-behaved.