Notesdistributed🌱 seedling
Consensus
Also: Distributed Consensus · Consensus Algorithm · State Machine Replication · Replicated State Machine
Getting a group of nodes to agree on one value (or one log, entry by entry) even though some may crash and the network may delay messages. Safety always holds; progress needs a majority up and a network that's usually timely.
Also in: Consensus › Majorities and terms
Why it exists
Failover, locks, uniqueness and configuration all need "exactly one" answer that every node accepts. Timeouts and scripts can be fooled by a slow network into Split Brain; consensus can't.
How it works
- Properties: agreement (no two nodes decide differently), integrity (decide once), validity (the value was proposed), termination (non-crashed nodes eventually decide).
- Majority quorums: a decision needs more than half the nodes; any two majorities overlap, so later decisions always learn of earlier ones. Terms / ballots / epochs number each leadership period, and messages from older terms are rejected.
- A log of decisions is Total Order Broadcast; deterministic replicas applying it stay identical (state machine replication).
- Equivalent problems: linearizable compare-and-set, a lock with one holder, leader election. Algorithms: Raft, Paxos (Multi-Paxos), Zab, Viewstamped Replication.
Trade-offs
| Gains | Costs |
|---|---|
| no split brain; committed means permanent | a majority round trip and fsync per decision |
| tolerates f failures with 2f + 1 nodes | minority side stops during a partition |
| one ordered history | one leader's throughput per group |
In practice
- Kafka 4.0 (2025) dropped ZooKeeper; metadata runs on its Raft-based KRaft controller quorum.
- DynamoDB: each partition's replicas form a Multi-Paxos group; millions of groups per Region.
Pitfalls
- Even cluster sizes: 4 nodes tolerate 1 failure, like 3, and can split 2 | 2.
- Putting consensus on the data hot path instead of metadata, or sharding into many groups.
- Two-Phase Commit is not fault-tolerant consensus: it blocks if the coordinator dies.
Connections
- Part of
- Distributed Systems
Recall
These cards are also in your review deck, scheduled with spaced repetition.