Consensus algorithms

TL;DR

• Consensus is the problem of getting N distributed nodes to agree on a single value, even when some nodes crash or messages get lost.
• In quorum-based replicated logs, once a value is committed by a majority, later protocol-compliant linearizable reads cannot return a conflicting committed value.
• Paxos (Lamport, 1989) proved consensus is solvable. Raft (2014) made it implementable by choosing clarity over generality.
• Quorum-based consensus protocols pay a latency cost: a write generally needs network coordination with enough replicas before acknowledgment.
• In interviews, consensus shows up whenever you need leader election, distributed locks, or linearizable configuration stores (etcd, ZooKeeper, Consul).

---

The Problem It Solves

You have three database nodes behind a load balancer. A user updates their email address. The write lands on Node A, which confirms success. Milliseconds later, the user refreshes the page, and the load balancer routes the read to Node C. Node C hasn't received the write yet. The user sees their old email and files a support ticket: "your update didn't work."

That's the mild version. Now imagine two clients simultaneously try to claim the last seat on a flight. Node A accepts Client 1's reservation. Node B accepts Client 2's reservation. Neither node knows about the other's decision. Without coordination, the system can double-book the flight.

Without consensus, every node operates on its own view of the world. Writes succeed locally with no coordination, and when the network heals, there's no principled way to decide which conflicting write wins.

This is the split-brain problem. Without a protocol that forces agreement before commitment, a replicated multi-node system can diverge during a partition. Replication copies state; consensus also coordinates which value is committed.

Quorum-based consensus algorithms solve this by requiring a majority of nodes to agree on each committed log entry. If the network splits, only a partition with a majority can continue making progress; the minority blocks rather than committing conflicting entries.

---

What Is It?

Consensus is a protocol that ensures a group of N nodes agrees on a single value for each decision slot despite some crashes or lost messages. A quorum-based protocol can remain safe with up to floor(N/2) unavailable nodes, but it can make progress only while it can reach a quorum and its timing assumptions hold.

Think of a jury. Twelve people must reach a verdict (or in many systems, a majority). Jurors deliberate, propose, and vote. If some jurors are absent, the remaining ones can still reach a verdict as long as enough are present. Once the verdict is reached, it's final; returning jurors don't get to overrule it.

In distributed systems, consensus provides three guarantees:

1. Agreement: all non-faulty nodes decide on the same value.
2. Validity: the decided value was proposed by some node (no fabrication).
3. Termination: all non-faulty nodes eventually decide (no infinite stalling).

The FLP impossibility result (Fischer, Lynch, Paterson, 1985) proved that no deterministic consensus algorithm can guarantee all three properties in a fully asynchronous system with even one crash failure. Practical algorithms use timeouts and partial-synchrony assumptions to make progress when the network behaves well enough.

In an interview, a concise explanation is: "A quorum-based consensus system commits only after a majority agrees; timeouts and election rules let it make progress under a partial synchrony assumption, while safety must hold during failures."

---

How It Works

Many production coordination systems use a Raft-like replicated log, so the walkthrough below uses Raft. Paxos solves the same problem with different terminology; the choice of protocol depends on the system and implementation constraints.

Raft: Leader Election

Every node in a Raft cluster is in one of three states: Follower, Candidate, or Leader. Time is divided into terms (logical epochs). Each term has at most one leader.

1. All nodes start as Followers, listening for heartbeats from the Leader.
2. If a Follower receives no heartbeat within a randomized election timeout (the exact value is deployment-specific), it transitions to Candidate and increments the term.
3. The Candidate votes for itself and sends RequestVote RPCs to all other nodes.
4. Each node votes for at most one candidate per term, and only if the candidate's log satisfies the election rules.
5. If the Candidate receives votes from a majority, it becomes Leader.
6. The Leader immediately sends heartbeats to all Followers to establish authority and prevent new elections.

The randomized election timeout makes it likely that one node times out before the others, reducing split votes. If candidates split the vote and neither gets a majority, they retry with new randomized timeouts. Randomness is a simple way to break election symmetry.

Raft: Log Replication

Once a leader is elected, client writes in a standard Raft deployment go through it. The leader appends each write to its log, replicates it to followers, and commits it after the protocol's quorum condition is satisfied.

1. Client sends write to Leader: set x = 5
2. Leader appends to its log: [term=2, index=42, cmd="set x 5"]
3. Leader sends AppendEntries RPC to all Followers
4. Each Follower appends the entry and responds with ack
5. Leader counts acks; once the protocol's majority condition is met, the entry can be committed
6. Leader applies committed entry to state machine and responds to client
7. On the next heartbeat, Leader tells Followers the new commit index
8. Followers apply committed entries to their state machines

The critical invariant is that a committed entry is protected by a majority and the election rules preserve it. Any future leader must be sufficiently up to date to win the election, so committed entries are not overwritten. The precise commit rule also includes Raft's current-term restriction, which the simplified sequence omits.