Replication, consensus & the impossibility results

Why does a majority quorum work?

Because any two majorities of the same set must overlap in at least one member. That is the entire mechanism, and everything else follows from it.

With 5 nodes, a write acknowledged by 3 and a read served by 3 must share at least one node, and that node has the write. So the read cannot miss it. Generalised: R + W > N guarantees a read set intersects every write set.

• N=3, W=2, R=2 — tolerates one failure, strongly consistent reads.
• N=3, W=3, R=1 — fast reads, no write availability if any node is down.
• N=3, W=1, R=1 — fast and available, eventually consistent. This is Cassandra/Dynamo's tunable default territory.

The same overlap property is why a partitioned cluster cannot elect two leaders: leadership requires a majority of votes, and there can only be one majority. The minority side knows it is a minority and steps down.

It is also why cluster sizes are odd. A 4-node cluster needs 3 for a majority — the same as a 5-node cluster — so it tolerates one failure instead of two while costing an extra machine. And a 2-node cluster tolerates zero failures, because a majority of 2 is 2.

How does Raft actually work?

Raft decomposes consensus into three pieces so it can be understood and implemented correctly, which was explicitly its design goal.

1. Leader election. Every node is a follower, candidate or leader, and time is divided into numbered terms. A follower that hears nothing from a leader within a randomised election timeout (150-300 ms) increments the term and becomes a candidate, voting for itself and requesting votes. A node grants its vote if the candidate's term is at least as new as its own, it has not already voted this term, and — critically — the candidate's log is at least as up to date as its own. A candidate with a majority becomes leader. The randomised timeout is what prevents perpetual split votes.

That log-completeness check is the subtle part: it guarantees that only a node containing every committed entry can win, which is what makes the next piece safe.

2. Log replication. All writes go to the leader, which appends to its log and sends AppendEntries to followers. Once a majority have persisted an entry, the leader marks it committed and applies it to its state machine, telling followers the new commit index. Each AppendEntries includes the index and term of the preceding entry; a follower that cannot match it rejects, and the leader walks backwards until they agree, then overwrites the follower's divergent suffix. This is how Raft repairs an inconsistent follower after a partition.

3. Safety. The properties that make it correct: at most one leader per term; a leader never overwrites its own log entries; if two logs contain an entry with the same index and term, all preceding entries are identical; and a committed entry is present in every future leader's log. There is one famously subtle rule — a leader may only mark entries from its own current term as committed by counting replicas, never entries from a previous term, because a majority-replicated-but-uncommitted old entry can still be overwritten. Knowing that rule exists is a strong signal; it is the source of several real implementation bugs.

In production you also need log compaction via snapshots (the log cannot grow forever), joint-consensus membership changes (adding and removing nodes safely), and read handling — since a stale leader that has not yet noticed it was deposed will happily serve stale reads. Fixes: ReadIndex (confirm leadership with a heartbeat round before serving), or leader leases (which trade a clock assumption for the round trip).

What do FLP and CAP actually say, and how do systems get around them?

FLP (1985): in an asynchronous system with even one faulty process, no deterministic algorithm can guarantee consensus. The reason is that you cannot distinguish a crashed node from a slow one, so any algorithm can be forced into indefinite indecision.

Real systems escape it with randomisation and timeouts: Raft's randomised election timeout means the probability of continued split votes decays exponentially. Consensus is not guaranteed to terminate — it terminates with probability 1, which is enough. That framing ("we trade guaranteed termination for probabilistic termination") is much stronger than reciting the theorem.

CAP: during a network partition, choose consistency or availability. The refinement worth knowing is PACELC: if Partitioned, choose A or C; Else, choose Latency or Consistency. Because partitions are rare, the everyday trade is latency versus consistency — synchronous replication costs a round trip on every write, and that is the choice you actually make daily.

The nuance that separates a good answer: CAP's C is linearizability, not ACID's C; "AP" systems are not unavailable-free, they are only available for the operations they can serve locally; and modern systems are tunable per operation rather than categorical — Spanner is effectively CP but uses TrueTime's bounded clock uncertainty to make it fast, and DynamoDB lets you choose eventual or strongly consistent reads per call.

What consistency models should you be able to place?

From strongest to weakest, with the cost of each:

• Strict serializability / linearizability — operations appear to happen instantaneously, in real-time order. Requires consensus, so at least one round trip to a majority. Spanner, etcd, CockroachDB.
• Serializable (transactions) — some serial order exists, not necessarily the real-time one. Postgres SSI achieves it by detecting conflicts and aborting, which is why you need a retry loop.
• Snapshot isolation — reads see a consistent snapshot; permits write skew, where two transactions read a consistent state and each writes something that jointly violates an invariant. This is the anomaly most people have never heard of and the reason SI is not serializable.
• Causal consistency — operations related by cause-and-effect are seen in order everywhere; concurrent ones may differ. Achievable without coordination (using vector clocks or Lamport timestamps), and sufficient for most social features: you never see a reply before the message it replies to.
• Read-your-writes / monotonic reads — session guarantees. The practical minimum for a usable UI, and cheaply implemented by pinning a session to the primary for a few seconds after a write.
• Eventual consistency — replicas converge if writes stop. Fine for a view counter, unacceptable for a balance.

The senior move is applying different models to different data in one system, and being explicit about which is which.

How do real databases replicate, and what breaks?

Single-leader (Postgres, MySQL, most of them). All writes go to one node and stream to followers.

• Asynchronous: the leader commits without waiting. Fast, but a failover loses the un-replicated tail — which is why "our database failed over cleanly" and "we lost 400 writes" are both true.
• Synchronous: waits for a follower's flush. No loss on failover, but every write pays a network round trip, and if the synchronous follower stalls, writes stop. Hence semi-synchronous: one synchronous replica, the rest async.
• Replication lag is the source of most application-visible weirdness — read-your-writes violations, a job processing a row that "does not exist" on the replica. And lag spikes precisely during incidents, because replay is largely serial while the primary writes in parallel.
• Failover is the dangerous part: choosing a new leader, ensuring the old one knows it has been deposed (or it becomes a split brain accepting writes nobody will keep), and reconciling divergent data. Automated failover with a bad health check causes more outages than the failures it protects against — worth saying, because it is a real, hard-won opinion.

Multi-leader — accept writes in several regions, replicate both ways. You now have write conflicts and must resolve them: last-write-wins (simple, and it silently discards data — with clock skew, the wrong write can win), application-defined merge, or CRDTs (data types whose merge is commutative, associative and idempotent, so convergence is automatic — counters, sets, and the collaborative-text types behind Yjs and Automerge).

Leaderless (Dynamo, Cassandra) — write to N, wait for W, read from R. Anti-entropy repairs divergence: read repair (fix on the read path when replicas disagree), hinted handoff (a temporary node holds writes for an offline one), and Merkle trees to find differences cheaply between large datasets. Conflicting concurrent writes are detected with version vectors, not wall clocks.

Why can't you have exactly-once delivery, and what do you have instead?

The sender cannot distinguish "the message was lost" from "the message arrived and the acknowledgement was lost." It must resend (risking duplication) or not (risking loss). No protocol removes the ambiguity — this is the Two Generals problem, and it is a genuine impossibility, not an engineering gap.

So you get at-least-once delivery plus idempotent processing, which together produce exactly-once effects. The crucial implementation detail is that the deduplication marker and the effect must commit atomically — one transaction inserting into a processed_messages table with a unique constraint and applying the change. Recording the message id in Redis while writing the effect to Postgres just relocates the failure.

Related patterns worth naming: the transactional outbox (write the row and the event in one local transaction; a separate relay publishes it — this is how you avoid dual-write inconsistency between a database and a broker), change data capture reading the replication log directly (which gives you exactly the database's own ordering), and sagas for multi-service workflows, where atomicity is replaced by compensating actions and the intermediate states are visible.

What about time, and why is it not a valid ordering mechanism?

Wall clocks drift, NTP can step time backwards, VMs jump after live migration. Therefore:

• Never order events across machines by created_at. Use a logical clock: a Lamport timestamp gives a total order consistent with causality; a vector clock additionally detects whether two events were concurrent, which is what you need to identify a genuine conflict rather than silently overwriting.
• Never use wall time for durations or leases. Monotonic clocks only.
• Last-write-wins is data loss with extra steps when clocks disagree — the write with the fast clock wins regardless of which actually happened later.
• The exception that proves the rule: Spanner's TrueTime uses GPS and atomic clocks to give a bounded uncertainty interval, and simply waits out the uncertainty before committing. That is how it achieves external consistency globally — by buying better clocks and paying commit latency for them. Knowing this is the answer to "can't we just synchronise clocks?": yes, at the cost of a satellite receiver in every datacentre and a few milliseconds per commit.

What does all this mean for a design interview?

The chain to be able to walk:

You cannot detect failure reliably (FLP) → so you use timeouts and randomisation, which means false positives → which means a node can be replaced while still alive → which means split brain → which is prevented by majority quorums → which requires an odd number of nodes and costs a round trip per write → which is why strong consistency is slower → which is why systems offer weaker models → which are safe only when the application tolerates the specific anomaly → which is why you choose a consistency model per data type, not per system.

And the practical corollary that most candidates miss: most systems do not need consensus. A single Postgres primary with a replica, idempotent writes, and a unique constraint solves the overwhelming majority of "distributed" problems. Consensus is for the small set of things that genuinely need coordinated agreement — leader election, configuration, cluster membership — and for those, you use etcd or ZooKeeper rather than writing it yourself. Being the person who says that, rather than designing a Raft cluster for a CRUD app, is the actual staff-level signal.