Consensus Algorithms
The problem
Multiple machines sometimes need to agree on a single value or decision — who's the leader, what's the next entry in a log — even though messages can be lost or delayed and any individual machine might fail mid-decision. Consensus algorithms are provably correct protocols for reaching that agreement anyway.
Why now
Distributed consistency models established that machines need to agree on data, but not the actual mechanism for reaching that agreement under failure. Concurrency and synchronization already solved a related problem (coordinating access) using locks on a single machine; consensus is the much harder version of coordination when there's no single machine to hold the lock on at all.
Mental model
Consensus is a structured voting process: a proposal is put forward, a majority of nodes must acknowledge it before it's considered committed, and the majority requirement is exactly what tolerates some nodes being down or unreachable — as long as more than half are alive and can talk to each other, the system can keep making progress and never disagree with itself.
Requires
- Distributed Consistency ModelsDistributed Systems
Consensus algorithms exist to implement strong consistency guarantees across unreliable machines; you need the specific consistency guarantee being sought before the mechanism that achieves it is well-motivated.
- Concurrency & SynchronizationOperating Systems
Consensus is coordination — the same problem locks solve on a single machine — solved without a single shared point of coordination at all; the goal (safe agreement under contention) is identical, only the tools differ.
Unlocks
Related
Used in
- Raft and Paxos, the two most widely implemented consensus algorithms
- etcd and ZooKeeper, coordination services built entirely around consensus, used by countless other systems
- Distributed databases' internal replication agreement (e.g. CockroachDB, TiDB use Raft)
- Leader election, which is consensus applied to the specific question 'who is in charge right now'
Projects
- Trace through a simplified Raft election by hand: five nodes, one crashes, walk through how the remaining four agree on a new leader
- Explain why a consensus algorithm requires a strict majority (not just 'some') of nodes to agree, using a split-brain scenario as the failure case being prevented
Examples
- etcd (which Kubernetes relies on for its own cluster state) uses Raft consensus to keep its data consistent across multiple nodes
- A 5-node Raft cluster can tolerate 2 node failures and still make progress, because 3 remaining nodes still form a majority
Resources
- The Raft Consensus Algorithmarticle
Mastery checklist
- I can explain what problem consensus algorithms solve and why simple majority voting is central to it
- I can trace through a simplified leader election under a node failure
- I can explain why an even split (no majority) must not be allowed to make progress
- I can name at least one real system built on Raft or Paxos