Distributed Consensus

When you actually need consensus, the algorithms (Paxos / Raft / Zab), and the CAP framing.

Overview

The protocol problem at the heart of reliability

Distributed consensus asks how N machines agree on a value when some may fail or be partitioned. It is not a footnote; it is the foundation under every piece of state that must stay consistent across machines.

When you need it (SRE Book Ch 23)

Leader election — Exactly one master
Group membership — Consistent view of who's in the cluster
Lease or lock validity — Exclusive grants
Reliable distributed queuing and message commitment — Agreement on what's been delivered
Datastore values — Consistent state across machines

The named algorithms

Paxos — Lamport, 1989 — The original. Proven correct, notoriously hard to implement. Most "Paxos in production" is Multi-Paxos, a leader-elected variant for sequences of values
Raft — 2014 — Designed for understandability; same guarantees as Paxos with clearer leader election. The default for new systems
Zab — ZooKeeper — Similar to Multi-Paxos in spirit
Mencius — Paxos variant — Geo-distributed, with rotating leadership

Theoretical limits

FLP impossibility (Fischer, Lynch, Paterson, 1985) — In an asynchronous network with even one faulty process, no deterministic algorithm guarantees both safety and liveness. Real systems use timeouts and randomized backoff, accepting that consensus may briefly block
CAP (Ch 23 framing) — Partitions are inevitable, so the real choice is consistency or availability during a partition

When not to use consensus

Read-heavy services tolerating stale reads — Caches and content delivery are fine stale
Eventually-consistent stores — Users tolerate seeing their write a few seconds later
Append-only logs without ordering needs — No agreement required

> [!WARNING] Consensus is expensive: every operation pays multiple round trips. Don't pay if you don't need to.

Key concepts

Distributed consensus: Protocol problem: N machines agree on a value despite failures or partitions. Required for leader election, distributed locks, coordinated state.
Paxos: Lamport, 1989. Proven correct, hard to implement. Most "Paxos in production" is Multi-Paxos with a stable leader optimization.
Raft: Designed for understandability (2014). Same guarantees as Paxos. Default choice for new systems. Used by etcd, Consul, CockroachDB.
FLP impossibility: Async network + 1 faulty process → no deterministic algorithm guarantees safety AND liveness. Real systems navigate via timeouts.
Quorum: Majority of replicas (⌊N/2⌋ + 1). 3 replicas tolerate 1 failure; 5 tolerate 2; 7 tolerate 3. Latency vs fault-tolerance trade-off.
CAP — partitions are inevitable: The real choice is C vs A during a partition. Spanner / Chubby choose C. DynamoDB / Cassandra choose A.

When to use it

Designing a system that needs leader election, distributed locks, or coordinated state across machines
Choosing between strongly-consistent (Spanner, Cockroach) and eventually-consistent (DynamoDB, Cassandra) datastores
Reviewing an architecture proposal that uses heartbeats for leader election (red flag — heartbeats don't prevent split-brain)
Capacity planning for a consensus-backed system — every op pays N round trips

Interview questions

When do you actually need distributed consensus?
Why is heartbeat-based leader election dangerous?
How do you decide between 3-replica and 5-replica consensus?