Consensus
Summary: The fundamental problem of getting several nodes in a distributed system to agree on something, such as a value or a sequence of events.
Sources: chapter9
Last updated: 2026-04-17
Consensus is one of the most important and fundamental problems in distributed computing (source: chapter9, p. 321). Informally, the goal is to get several nodes to agree on something (source: chapter9, p. 364).
Properties
A consensus algorithm must satisfy the following properties, even if some nodes fail (source: chapter9, p. 365):
- Uniform agreement: No two nodes decide differently.
- Integrity: No node decides twice.
- Validity: If a node decides value v, then v was proposed by some node.
- Termination: Every node that does not crash eventually decides some value.
The termination property is what makes consensus fault-tolerant (source: chapter9, p. 365).
The FLP Result
The Fischer, Lynch, and Paterson (FLP) result proves that in an asynchronous system model (no clocks or timeouts), there is no algorithm that is always able to reach consensus if there is a risk that even one node may crash (source: chapter9, p. 353). However, in practice, consensus is achievable using timeouts or randomization (source: chapter9, p. 353).
Consensus Algorithms
The best-known fault-tolerant consensus algorithms are:
- Paxos: The classic (but complex) algorithm (source: chapter9, p. 366).
- Raft: Designed to be easier to understand than Paxos (source: chapter9, p. 366).
- Zab: Used by ZooKeeper (source: chapter9, p. 366).
- Viewstamped Replication (VSR) (source: chapter9, p. 366).
These algorithms actually decide on a sequence of values, which makes them total-order-broadcast algorithms (source: chapter9, p. 366).
Single-Leader Replication and Consensus
Single-leader replication depends on consensus for leader election (to avoid split-brain) (source: chapter9, p. 367). However, consensus algorithms themselves often require a leader to be efficient. This is solved by using an epoch number (or ballot number, view number, term number) to ensure that within each epoch, the leader is unique (source: chapter9, p. 368).
Limitations
- Fixed Membership: Most consensus algorithms assume a fixed set of nodes, which makes dynamic membership (adding/removing nodes) difficult (source: chapter9, p. 369).
- Performance: Consensus algorithms are generally slower than simple replication due to the cost of rounds of voting (source: chapter9, p. 369).
- Network Sensitivity: They can be sensitive to network delays and timeouts (source: chapter9, p. 369).