The Consensus Problem

Consensus is the problem of getting several nodes to agree on a single value even though some may fail or the network may reorder messages. It’s the foundation under leader election, distributed locks, replicated state machines (databases), and configuration. The stakes: if two nodes believe they are both the leader, you get split-brain — two writers producing contradictory state.

The fundamental result (FLP, 1985) says that in an asynchronous network, deterministic consensus is impossible if even one node can crash. Real systems escape this by being practical: they add timeouts to break ties, so progress is not guaranteed but is achieved almost always. That’s the honest engineering bargain behind every real consensus algorithm.

Paxos: The Elegant Foundation

Paxos (Leslie Lamport, 1989) solves single-value consensus with roles proposers, acceptors, and learners:

1. Prepare — a proposer sends a prepare with a ballot number n; acceptors promise not to accept ballots < n and reply with any value they already accepted.
2. Accept — once a proposer hears from a majority, it sends an accept for its value; acceptors accept it if they haven’t promised a higher ballot.
3. Learn — once a majority accepts, the value is decided and propagated.

The key safety invariant: because any two majorities overlap in at least one acceptor, a later proposer must learn the value an earlier majority accepted and must not propose a conflicting value. The classic paper’s tragedy is its (in)famous difficulty to read — which is exactly why Raft exists.

Raft: Consensus You Can Actually Understand

Raft (Diego Ongaro, 2014) decomposes consensus into three subproblems:

1. Leader election — nodes are follower, candidate, or leader. Followers with no heartbeat from a leader time out and become candidates, incrementing their term, requesting votes. A candidate wins with a majority quorum and sends heartbeats to suppress further elections.
2. Log replication — the leader is the only writer. Clients write to the leader; it appends the entry to its log and sends it to followers; when a majority has it, the entry is committed and applied to the state machine.
3. Safety — election restriction (a candidate must have the most up-to-date log) + commit rules guarantee a committed entry is never overwritten. Terms and log indexes provide the total ordering.

The Log is the state machine’s durable, ordered history — every follower ends up with the same log, and therefore the same state. This is the replicated state machine pattern: consensus on the log, then deterministic execution of the log, gives you distributed databases (etcd, ZooKeeper, Consul, CockroachDB, TiKV).

Quorum and Fault Tolerance

A cluster with N nodes needs a majority ⌊N/2⌋ + 1 to elect a leader and commit. This buys fault tolerance: with 3 nodes you survive 1 failure; with 5, you survive 2. It also means minority-partitioned nodes cannot elect a leader — they stall (CP behavior) rather than risk split-brain. This is the direct CAP trade: Raft picks consistency over availability during a partition.

Failure Modes to Know

• Split vote — three candidates, no majority; random election timeouts make a retry win.
• Leader partitioned — the old leader (cut off from quorum) can’t commit but may still be receiving client requests it can’t acknowledge; clients must time out and retry to a reachable node.
• Stale leader serving reads — the classic reason to read through a quorum or ReadIndex: a partitioned leader might serve stale reads until its term ends. Raft’s log read / read-index mechanisms (or routing reads through the leader with a quorum check) prevent this.
• Log mismatch — a follower that fell behind must be brought up to date; Raft’s leader forces its log via the AppendEntries consistency check (find last common index, then replicate forward).

The Visualizer

Use the Raft visualizer above to watch two scenarios. First, an election: a follower’s timer expires, it becomes a candidate with a new term, votes are solicited, and a leader emerges (or a split vote resolves). Second, log replication: a client write hits the leader, appends to the log, replicates to followers, and commits once a majority acknowledges.

Real-World Consensus

• etcd / Consul / ZooKeeper — Raft-based coordination backends. Kubernetes stores all cluster state in etcd; Consul/ZooKeeper power service discovery, locks, and config.
• Google Spanner — Paxos (with a twist: TrueTime) across regions, one of the few globally-consistent databases.
• Raft as a building block — every distributed DB worth its salt embeds Raft/Paxos for its replicated log.

Practice Trajectory

1. Trace an election with 3 nodes: one follower times out, becomes candidate, wins with 2 votes, starts heartbeats.
2. Simulate a split vote with three simultaneous candidates and explain how randomized timeouts break the tie.
3. Given a 5-node cluster, show a client write committing after 3 acknowledgments, and a follower that failed catching up.
4. Explain why a minority partition can never elect a leader — and why that is the price of safety.
5. Compare where etcd, ZooKeeper, and Consul sit on the CP/AP axis and what coordination use-cases they serve.

When It’s the Right Tool