Distributed systems theory

Most of this will never be asked directly. That is not the point.

The point is that a candidate who knows why consensus needs a majority, or what linearizability actually promises, gives shorter and more confident answers to ordinary questions. Depth leaks upward. An interviewer probing “what if the network partitions here?” can tell within one sentence whether you have a model or a memorised phrase.

Budget: this is Week 5–6 material, and it is the first thing to cut if coding is weak. A strong coding round with shallow theory passes; the reverse does not.

Read it in this order. Each section assumes the one before.

Contents

1. The system model: what “asynchronous” costs you
2. FLP: why consensus has no perfect algorithm
3. Failure detectors: the practical escape from FLP
4. Time, causality, and clocks
5. Quorums: the arithmetic
6. Consensus: Raft at interview depth
7. Linearizability vs serializability
8. CAP, stated precisely
9. CRDTs: convergence without coordination
10. What to actually say

1. The system model: what “asynchronous” costs you

Every distributed systems result depends on three assumptions people usually leave unstated. Naming them is most of the battle.

Timing. In a synchronous system, message delay and processing time have known upper bounds. In an asynchronous system they do not — a message may take arbitrarily long. Partial synchrony sits between: bounds exist but you do not know them, or they only hold after some unknown point.

Real networks are partially synchronous. Usually fast, occasionally arbitrarily slow, and you cannot tell the two apart from inside.

Failures. Crash-stop: a node halts and stays halted. Crash-recovery: it halts and comes back, possibly having lost volatile state. Byzantine: it behaves arbitrarily, including maliciously.

Within one datacentre you assume crash-recovery. Byzantine tolerance costs 3f + 1 nodes instead of 2f + 1 and is the domain of blockchains and adversarial settings — mentioning that you are not assuming Byzantine faults, and why, is a nice precise touch.

The one thing you cannot do. In an asynchronous system you cannot distinguish a crashed node from a slow node. There is no test. Every timeout is a guess, and every failure detector is therefore fallible.

Almost everything below follows from that single limitation.

Why it pays: when an interviewer asks “how do you know the leader is dead?”, the honest answer is “I don’t — I know it hasn’t responded within a timeout I chose, and I’ve designed for being wrong.” That answer is worth more than any mechanism.

2. FLP: why consensus has no perfect algorithm

Fischer, Lynch and Paterson (1985). In an asynchronous system, with even one possible crash failure, there is no deterministic algorithm that guarantees consensus.

What consensus requires

Three properties. The impossibility comes from insisting on all three at once:

• Agreement — no two correct nodes decide different values.
• Validity — the decided value was proposed by some node.
• Termination — every correct node eventually decides.

The intuition behind the proof

You do not need the proof. You need the shape of it, which is one paragraph:

There must exist some initial configuration from which the outcome is not yet determined — call it bivalent, meaning both decisions are still reachable. Show that from any bivalent configuration, an adversary controlling message delivery order can always delay exactly one message and reach another bivalent configuration. Since the system can be kept bivalent forever, it never decides. Termination fails.

The adversary’s only power is delaying a message, not corrupting it. That is what makes the result so strong — and so unsettling.

What it does and does not mean

It does not say consensus is impossible in practice. Paxos, Raft and Zab are all used daily. It says no algorithm can guarantee all three properties in an asynchronous model.

Real algorithms give up guaranteed termination. They always preserve safety (agreement and validity) and guarantee progress only when the network behaves — “eventual” liveness under partial synchrony. A Raft cluster under a pathological network can keep holding elections and never commit. It will never commit two conflicting values, which is the property that matters.

The sentence that scores: “Raft never sacrifices safety. Under a bad enough network it sacrifices liveness — it stops making progress rather than committing something it might have to take back. FLP says that tradeoff is unavoidable.”

3. Failure detectors: the practical escape from FLP

If the obstacle is not being able to tell crashed from slow, formalise the imperfect guess.

Chandra and Toueg defined failure detectors by two properties:

• Completeness — every crashed node is eventually suspected.
• Accuracy — correct nodes are not suspected. Strong accuracy means never; eventual weak accuracy means that eventually some correct node stops being suspected.

Their key result: consensus becomes solvable with ◇W (“eventually weak”) — the weakest detector that works. This is the formal counterpart of “assume the network eventually behaves for long enough to elect a leader and commit.”

In practice

Timeout-based. Simple, and the timeout is a direct latency/accuracy tradeoff. Short timeouts detect real failures fast and produce false positives under load — exactly when a false positive is most damaging, because a spurious failover adds load to an already-struggling system.

Phi-accrual (used by Cassandra and Akka). Instead of a boolean, output a suspicion level φ derived from the distribution of recent heartbeat arrival times. The application picks its own threshold, and the detector adapts to a network that is naturally getting slower. Worth naming — it shows you know failure detection is a tunable component, not an if statement.

Gossip-based. Nodes share heartbeat counters; suspicion propagates. Scales to large clusters where all-to-all heartbeating would not.

The consequence you must design for

A false positive means two nodes believe they are the leader. That is split brain, and it is how data is lost.

Two defences, and you should know both:

• Fencing tokens. The lock service issues a monotonically increasing number with each grant. Storage rejects any write carrying a token lower than the highest it has seen. A revived old leader is now harmless — its writes are refused, without the storage layer needing to know anything about leadership.
• Leases. A leader holds time-bounded authority and must renew. If it cannot renew, it demotes itself before the lease expires. This shifts the correctness argument onto clock rate (which is reliable enough) rather than clock synchronisation (which is not).

The sentence that scores: “I’d use a lease plus fencing tokens, so a leader that got partitioned and came back cannot corrupt state — storage rejects its stale token.”

4. Time, causality, and clocks

Why wall-clock time is not usable for ordering

Clocks drift. NTP corrects by stepping — time can jump forward, and go backwards. Two events a millisecond apart on different machines cannot be ordered by timestamp with any confidence.

Concretely: last-write-wins using wall-clock timestamps silently loses writes. A node with a fast clock wins every conflict regardless of what actually happened first. If you propose LWW, say that out loud — proposing it knowing the flaw reads completely differently from proposing it in ignorance.

Lamport clocks

A counter per node. On a local event, increment. On send, attach the counter. On receive, counter = max(local, received) + 1.

Gives you: a → b (a happened-before b) implies L(a) < L(b).

Does not give you the converse. L(a) < L(b) does not mean a caused b — they may be concurrent. A single counter cannot represent concurrency.

Useful as a total order for tie-breaking (append the node ID to break equal counters). Not useful for detecting conflicts.

Vector clocks

A vector of counters, one entry per node. On a local event, increment your own entry. On send, attach the vector. On receive, take the element-wise max, then increment your own.

Now comparison is exact:

• V(a) < V(b) (every entry ≤, at least one strictly <) → a happened before b
• V(b) < V(a) → b happened before a
• Neither → concurrent, i.e. a genuine conflict

That third case is the payoff: vector clocks detect conflicts instead of silently resolving them wrongly. Dynamo used them to hand siblings back to the application.

The cost, which you should volunteer: the vector grows with the number of nodes that have ever written. In a system with many clients this becomes expensive, which is why version vectors are usually kept per replica rather than per client, and pruned.

TrueTime, and what Spanner bought with it

Spanner’s clocks report an interval [earliest, latest] rather than an instant, with the uncertainty bounded by GPS and atomic clocks — typically a few milliseconds.

The trick: to commit, a transaction waits out the uncertainty. It sleeps until it is certain its timestamp is in the past, then commits. That deliberate wait is what buys external consistency (linearizability across the whole globe).

So Spanner did not abolish the problem — it bought a bound on clock uncertainty with hardware, then paid latency to convert that bound into correctness. State it that way; it is the crispest one-line summary of the paper and exactly the “what did it trade?” framing that scores.

Hybrid logical clocks

Combine a physical timestamp with a logical counter. You get causality tracking like Lamport clocks, plus timestamps that stay close to wall-clock time so they remain human-meaningful and usable for TTLs. Used by CockroachDB. A good thing to name when someone asks how to order events without Google’s hardware budget.

5. Quorums: the arithmetic

With N replicas, writing to W and reading from R:

R + W > N guarantees the read set and the write set overlap, so a read sees at least one replica holding the latest write.

The pigeonhole argument in one line: two sets drawn from N whose sizes sum to more than N cannot be disjoint.

Why consensus clusters are odd-sized

A majority of N is ⌊N/2⌋ + 1, tolerating f = ⌊(N−1)/2⌋ failures.

• N=3 tolerates 1
• N=4 tolerates 1 — the same, for more cost and more latency
• N=5 tolerates 2

Even sizes buy nothing. Beyond 5 or 7, every commit waits on a larger majority, so latency rises while the marginal availability gain shrinks. That is why real clusters are 3 or 5, and being able to explain why — rather than just knowing the convention — is the depth worth having.

Sloppy quorums and hinted handoff

During a partition, accept writes on any W reachable nodes, even ones that do not normally own the key. Availability goes up; the R + W > N guarantee is temporarily void. The temporary holder keeps a hint and hands the data back when the real owner returns.

This is a deliberate, named tradeoff — exactly the kind of thing to raise yourself rather than wait to be asked.

6. Consensus: Raft at interview depth

You will not be asked to implement it. You may well be asked how leader election works, or what happens to an in-flight write during a failover.

Three sub-problems

Raft’s contribution was decomposing the problem so humans can reason about it: leader election, log replication, safety.

Terms

Time is divided into terms, each with at most one leader. The term number is a logical clock: any message carrying a term higher than yours makes you step down and update. This single rule eliminates most split-brain reasoning.

Election

Each follower runs a randomised election timeout. On expiry it becomes a candidate, increments the term, votes for itself, and requests votes. A candidate winning a majority becomes leader.

The randomisation is not incidental — it is what breaks symmetry. With fixed timeouts, nodes would repeatedly time out together, split the vote, and retry forever. That is FLP’s livelock showing up in practice, and randomisation is the standard escape.

Log replication

The leader appends to its log and sends AppendEntries to followers. Once a majority have persisted an entry, it is committed and can be applied.

The Log Matching property: if two logs contain an entry with the same index and term, then the logs are identical up to that point. Followers reject an append whose predecessor does not match, and the leader walks back until it finds agreement. Divergent tails get overwritten.

The safety rule people miss

A candidate can only win if its log is at least as up to date as the voter’s — compared by (last term, last index). This guarantees a new leader already holds every committed entry, so committed data is never lost in a failover.

Without this rule, a node with a stale log could win and truncate committed entries. This is the single most important detail in Raft, and the one that distinguishes having read the paper from having read a summary.

What it costs

Every commit needs a round trip to a majority. Within a datacentre that is sub-millisecond; across continents it is tens of milliseconds, per write.

That is precisely why consensus is used for metadata and coordination — cluster membership, shard assignment, leader locks, configuration — and almost never on the per-request data path.

The answer to “what happens to an in-flight write during failover?”

If it was committed (a majority persisted it), the new leader has it — guaranteed by the up-to-date-log rule. If it was not, it may be silently dropped. The client saw a timeout, not a success, so it must retry — and that retry must be idempotent or you will double-apply it.

That answer connects consensus to idempotency keys, which is exactly the kind of cross-topic link that reads as senior. Lab 5 in 09-hands-on-labs.md implements the idempotency half.

7. Linearizability vs serializability

Constantly conflated. Knowing the difference is a cheap, high-yield differentiator.

Linearizability is about single-object, real-time ordering. Every operation appears to take effect instantaneously at some point between its invocation and its response. If write A completes before read B begins (in real time), B must see A. It is a recency guarantee.

Serializability is about multi-object transaction ordering. Concurrent transactions produce a result equivalent to some serial execution. It says nothing about which order, and nothing about real time — a serializable system may legally order a transaction that started later as if it ran first.

They are orthogonal:

Strict serializability = serializable + linearizable. The strongest, most expensive guarantee, and what Spanner pays its commit-wait for.

The sentence that scores: “I need linearizability on this counter, but the reporting path only needs snapshot isolation — those are different guarantees and I don’t want to pay for the stronger one twice.”

8. CAP, stated precisely

The precise statement

During a network partition, a distributed system cannot provide both availability (every request to a non-failing node gets a non-error response) and consistency (linearizability).

What it is not

• Not “pick two of three.” Partition tolerance is not optional — networks partition whether or not your design acknowledges it. The choice is A or C, and only during a partition.
• Not about latency. CAP says nothing about normal operation.
• Not per-system. It is per-operation. One service can serve strongly consistent balance transfers and eventually consistent view counts.

PACELC, which is the more useful tool

if (P)artitioned, choose (A)vailability or (C)onsistency; (E)lse, choose (L)atency or (C)onsistency.

The else branch is where your system spends 99.9% of its life, and it is the interesting tradeoff: every synchronous replication or consensus round trip you add is latency you pay all day, to make the rare partition safer.

Classifications worth knowing: Spanner is PC/EC (consistent in both branches, paying latency for it). Cassandra and Dynamo are PA/EL (available and fast, consistency relaxed). DynamoDB with strong reads is PC/EC on that path and PA/EL otherwise — which is itself the point that CAP is per-operation.

The sentence that scores: “During a partition I’d stay available here and reconcile after, because a stale count is acceptable. But even with no partition I’m choosing latency over consistency on this path, and that means clients must tolerate a stale read.”

9. CRDTs: convergence without coordination

The question CRDTs answer: can replicas accept writes independently and still converge, with no coordination and no conflict resolution callback?

Yes — if every merge operation is commutative, associative and idempotent. Those three properties mean the merge result is independent of the order and multiplicity of message delivery, which is exactly what an unreliable network gives you.

The types worth naming

• G-Counter — per-node counters; merge takes the element-wise max, value is the sum. Increment-only.
• PN-Counter — two G-Counters, one for increments and one for decrements.
• G-Set — add-only; merge is union.
• LWW-Register — last write wins by timestamp. Simple, and it loses data; it is only a CRDT in the sense that it converges, not that it preserves intent.
• OR-Set (observed-remove) — tags each addition with a unique ID; a remove only removes the tags it observed. Solves add/remove ordering properly, at the cost of tombstones, which must eventually be garbage-collected.
• RGA / sequence CRDTs — ordered sequences for collaborative text editing.

State-based vs operation-based

State-based (CvRDT): ship the whole state, merge with a join function. Robust to duplicate and reordered messages, but bandwidth-heavy. Deltas mitigate.

Operation-based (CmRDT): ship operations. Cheap, but requires exactly-once, causally-ordered delivery — which pushes the hard problem back into the transport layer.

Where they actually fit

Good for: collaborative editing, shopping carts, presence, counters that may be approximate, offline-first mobile sync.

Bad for: anything with a global invariant. A CRDT cannot enforce “balance must never go negative”, because two replicas can independently approve withdrawals that are individually valid and jointly not. Invariants that span replicas need coordination — CRDTs are precisely the technique for when you can avoid needing it.

Saying that — naming what CRDTs cannot do — is worth more than listing six types.

CRDT vs OT: operational transformation (Google Docs) transforms concurrent operations against each other, and classically needs a central server to define an order. CRDTs need no server but carry more metadata. If collaborative editing comes up, name both and give the tradeoff.

10. What to actually say

Theory earns its keep in one-sentence form. The goal is never a lecture — it is a precise clause dropped into an ordinary answer.

The trap

Do not volunteer theory that is not load-bearing. Saying “by FLP…” when the question was about caching reads as showing off, and showing off is scored negatively under Googleyness.

Use it when it answers the question more precisely than the plain-English version would. That is the whole test.

If you want to go further

Not required for the loop, listed in the order that repays effort:

• Designing Data-Intensive Applications, Kleppmann — chapters 5, 7, 9 cover replication, transactions, and consistency better than any summary.
• The Raft paper — genuinely readable, unlike Paxos.
• Time, Clocks, and the Ordering of Events, Lamport (1978) — short, and the origin of half this page.
• Jepsen reports — real databases violating their documented guarantees. The best available cure for taking marketing claims at face value.