Concrete scenario
Three metadata nodes replicate a log; one crashes and messages between the remaining nodes are delayed.
Mechanics
Consensus protocols such as Raft and Paxos maintain safety through terms or ballots, quorum intersection, and durable log rules. Liveness requires assumptions stronger than a fully asynchronous network, commonly eventual synchrony plus fair scheduling; randomized election timeouts reduce repeated split votes but do not by themselves defeat FLP.
Failure mode
Without a majority, a safe cluster cannot commit new entries. A stale leader may still contact external systems, membership changes can break quorum assumptions if done incorrectly, and snapshots or log repair can prolong recovery.
Trade-off
Consensus is a foundation for replicated state, leader election, and coordination, not a complete solution for atomic external side effects or application invariants. It adds write latency and operational discipline in exchange for a durable agreed order.
Worked example: quorum sizing and latency
A Raft group replicates a metadata log. A commit needs acknowledgements from a majority, counting the leader.
| Cluster size N | Majority | Failures tolerated | Write latency (leader in site 1) |
|---|---|---|---|
| 3 (one zone) | 2 | 1 | About 1 ms: one fast LAN round trip plus fsync |
| 3 (three zones, same region) | 2 | 1 (or one zone) | About 2 to 3 ms |
| 5 (three regions: 2+2+1) | 3 | 2 (or one region) | Round trip to the nearest other region, about 30 to 80 ms |
| 4 | 3 | 1 | Same fault tolerance as 3 but slower. Avoid even sizes |
Each commit also needs a durable fsync on each acknowledging node. On cloud SSDs that is typically 0.5 to 2 ms, which is why etcd's documentation stresses low-latency disks.
What consensus guarantees
- Agreement: no two nodes decide different values for the same log slot.
- Validity: the decided value was proposed by someone.
- Termination: guaranteed only when the network is stable enough. FLP (1985) proves no deterministic protocol can guarantee it in a fully asynchronous system with even one crash.
Paxos, Raft and friends
| Protocol | Key idea | Where it runs |
|---|---|---|
| Multi-Paxos | A stable leader skips phase 1 for successive slots | Chubby, Spanner (per split), many Google systems |
| Raft | A strong leader, term numbers, and a log-matching property. Designed for understandability | etcd, Consul, CockroachDB, TiKV, Kafka KRaft |
| Zab | Primary-backup atomic broadcast with epochs | ZooKeeper |
| Viewstamped Replication | View changes, predating Paxos's publication | Academic, and the basis for some storage systems |
| PBFT / HotStuff | Byzantine tolerance with 3f+1 nodes | Permissioned blockchains |
Failure modes seen in production
- Disk stalls make the leader miss heartbeats, which triggers election churn.
- Membership changes done by editing config files on each node can create two disjoint majorities. Use joint consensus or single-server changes.
- Log growth without snapshots makes restarts replay millions of entries.