Distributed Fundamentals: Partial Failure, Quorums, Consensus, Recovery

A single-node database fails all at once: the process is running or it is not, and a crash is detected by the operating system in microseconds. A distributed database fails partially: node B is down while A and C are up; the link between A and B is cut while both are fine; C is paused for 20 seconds by a garbage collector or a VM migration and then resumes as if nothing happened. And the only failure detector available is a timeout — "no reply within 5 s" — which cannot distinguish a dead node from a slow one from a working node behind a broken link. Networks also reorder, duplicate and delay messages, so "I sent the write and got no reply" leaves three possibilities: it was lost, it was applied and the reply was lost, or it is still in flight.

Every mechanism in this lesson is an answer to one question: how can a group of nodes act safely on incomplete and possibly wrong information about each other? The recurring answer is that no single node's opinion is trusted; decisions require a majority, and every decision is numbered so that a node acting on stale information can be recognised and refused.

Two copies of the data are divergent when each holds acknowledged writes the other lacks. Divergence is not lag — a lagging replica is a prefix of the leader and will converge by replaying; a divergent one has a different suffix and cannot converge without discarding something. It arises whenever two nodes each accept writes for the same data without coordinating: a partitioned old leader and a newly elected one (split brain), two coordinators in a leaderless store with W = 1, or a paused leader that wakes up and serves one more write after its replacement took over.

The leader/follower design prevents divergence by construction — one writer, an ordered log, followers that only apply — as long as there is only ever one leader. The majority rule is what makes "only ever one" enforceable: a node may act as leader, commit a write, or recognise a leader only with the agreement of more than N/2 nodes. Two majorities of the same set always share a member, so two leaders cannot both hold majorities in the same term, and a partition can at most leave one side able to proceed. With N = 3 this tolerates one failure; N = 5 tolerates two; even N buys nothing (4 nodes still tolerate only one, since 2 is not a majority of 4).

A leaderless replicated store sends every write to all N replicas and calls it successful when W have acknowledged; a read asks R replicas and returns the newest version among their answers. If W + R > N, the set of replicas that acknowledged the last write and the set the read consulted must overlap in at least one replica — so the read sees the latest acknowledged write. With N = 3: W = 2, R = 2 gives the overlap and tolerates one dead node for both reads and writes. W = 3, R = 1 makes reads cheap and writes impossible with any node down. W = 1, R = 1 is fast and tolerates two dead nodes, and a read may miss every replica that has the latest write. The numbers are chosen per operation — Cassandra's QUORUM, ONE, ALL, LOCAL_QUORUM; DynamoDB's consistent-read flag — which is why one system can be CP for the ledger and AP for the shopping cart.

The overlap guarantee is weaker than it looks. It holds among the replicas that *acknowledged*; a replica that was down or slow during the write is not in the overlap set and, if the read picks it and one other, may still see stale data unless W + R > N accounts for it (sloppy quorums and hinted handoff make this worse, not better). Concurrent writes to the same key with W < N can leave replicas holding different "latest" versions with no way to order them — hence version vectors, read repair (the reader writes the newest version back to stale replicas), and anti-entropy (background Merkle-tree comparison). And "newest" needs an ordering, which is where Lamport comes in.

Wall clocks on different machines disagree by milliseconds at best and by seconds after a bad NTP step, so "the write with the later timestamp is newer" is a guess that last-writer-wins systems make and sometimes get wrong. Lamport's observation: what matters is causality, not time. Give every node a counter; increment it before each local event; attach it to every message; on receiving a message, set the counter to max(local, received) + 1. Then if event a could have influenced event b (same node earlier, or a message from a's side to b's), stamp(a) < stamp(b) — a total order consistent with causality, obtained with no clock at all. It cannot tell you that two events were *concurrent* (independent); for that, vector clocks keep one counter per node and compare component-wise: a ≤ b in every component means a happened before b, otherwise they are concurrent and a conflict must be resolved. Raft's (term, index) pair is a Lamport clock specialised to a single log; Spanner's TrueTime is the expensive alternative of making wall clocks trustworthy with GPS and atomic clocks plus an explicit uncertainty interval.

Consensus is the problem of getting N nodes to agree on one value — in practice, on the next entry of a shared log — despite crashes and partitions. Raft solves it in five sentences. Time is divided into numbered terms; every message carries its sender's term, and any node that sees a higher term adopts it and, if it was leader, steps down. A follower that misses heartbeats becomes a candidate, increments the term, and requests votes; a majority makes it leader, and a node refuses to vote for a candidate whose log is less complete than its own (lower last term, or same term and shorter). The leader appends client commands to its log and replicates them with AppendEntries carrying the previous entry's index and term, so a follower with a conflicting suffix rejects, is walked back, and truncates. An entry is committed when the leader has it on a majority; the leader then applies it and advertises the commit index. Because leaders come from the most complete logs and never delete their own entries, a committed entry is in every future leader's log — nothing acknowledged is ever lost while a majority survives.

What you get from this: exactly one leader per term (two majorities share a voter, and a voter votes once per term), no acknowledged write lost across any sequence of failures that leaves a majority, and automatic, safe failover — the property the naive design could not provide. What it costs: a majority round trip per commit (two across regions), 2f + 1 nodes to tolerate f failures, and a leader that must stop serving when it cannot reach a majority (the lease: heartbeat replies prove the majority still recognises it; without them it must assume it has been replaced). Paxos reaches the same guarantees with a different decomposition; Multi-Paxos in practice looks like Raft. Every strongly consistent distributed database is one of these protocols with a storage engine as the state machine — CockroachDB runs a Raft group per 512 MB range; etcd is one Raft group and a key-value store; Patroni runs no Raft itself but rents a leader lease from one.

The failure simulator below lets you produce each of these. The table is the answer key: for each failure, what survives, what becomes unavailable, whether stale reads occur, and what must happen before the cluster is whole again. Notice that in a leader-based CP system every recovery is one of two operations — replay (a prefix catches up) or truncate then replay (a divergent suffix is discarded, then the node catches up) — and that the only writes ever discarded are ones the protocol never acknowledged, *unless* fencing was missing. In a leaderless AP system there is no truncation; divergence is merged, and last-writer-wins merges by losing.