10 · Distributed Systems

This chapter is the floor where "the computer" stops being a noun — the machine is now many machines, and the abstraction of one is something you have to build.

What breaks when there is no "now"?

At 22:52 UTC on 21 October 2018, engineers replacing failing optical equipment briefly severed the link between GitHub's East Coast network hub and its primary East Coast data center. Connectivity was restored in forty-three seconds. In those seconds the system that keeps the databases healthy did exactly what it was built to do: unable to reach the East Coast primaries, it promoted replicas on the West Coast. Writes had by then been accepted on both coasts. Neither side was wrong, neither could be discarded, and reconciling them took twenty-four hours and eleven minutes (GitHub post-incident analysis).

Nothing failed. That is the shape of every hard problem on this floor. The link came back, the machines were healthy, the failover logic was correct — and the system still could not say what had happened, because for forty-three seconds there was no shared answer to the question what is true right now.

Start with why that question has no easy answer. Two machines have two clocks, clocks drift, and no amount of care makes a timestamp from one comparable with a timestamp from the other. Leslie Lamport's response, in 1978, was to stop asking for time and ask only for order. His "happened before" relation says one event precedes another if they occur in sequence on the same machine, or if the first is the sending of a message and the second its receipt — plus whatever follows by chaining those together. Everything else is concurrent: genuinely unordered, so that any consistent story about which came first is as good as any other (Lamport, CACM 21(7), 1978). Physics reached this first: simultaneity is not absolute, and the only real ordering is the one causation can carry. In a distributed system, messages are the light cones.

The second difficulty is worse, because no formalism softens it. On one machine a component either works or has crashed. Across machines there is a third state indistinguishable from the other two: no answer yet. A silent peer may be dead, overloaded, or healthy behind a broken link, and no timeout separates these: a timeout says the answer has not arrived, never that it will not. Lamport's much-quoted definition captures what this does to the experience of building anything: "A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable" (Lamport, 28 May 1987). Failure here is not an event. It is an ambiguity.

Given ambiguity, can machines at least agree on one value — which replica is primary, which transaction committed, who holds the lock? This is the consensus problem, and it is the hardest thing here. Fischer, Lynch and Paterson proved in 1985 that in an asynchronous system, where messages can be delayed arbitrarily, no deterministic protocol can guarantee that all correct processes decide if even one process may crash (JACM 32(2): 374–382). The proof is not about bad engineering. It is the impossibility of telling a dead process from a slow one, elevated into a theorem.

Working systems live inside that result. Paxos, and Raft after it, never sacrifice safety — they will not decide two different values. What they give up is the promise to decide promptly: during a bad enough network they make no progress, and when it recovers, they do. Lamport submitted Paxos in 1990 as an archaeological account of a fictional Greek parliament, and it went unpublished for eight years while reviewers puzzled over the joke (ACM TOCS 16(2), 1998); he later wrote a four-page version, "Paxos Made Simple". Diego Ongaro and John Ousterhout's Raft made understandability an explicit design goal and won a best-paper award for it (USENIX ATC '14). GitHub's failover ran on Raft. Raft did not malfunction; it agreed, correctly and quickly, on the wrong thing.

Because consensus costs round trips, systems trade it away. Eric Brewer proposed in a July 2000 keynote that consistency, availability and partition tolerance cannot all be had (PODC keynote); Seth Gilbert and Nancy Lynch made the conjecture a theorem in 2002 (SIGACT News 33(2)). The popular reading — pick two of three — is wrong, and Brewer said so twelve years later: partitions are a fact of networks, not a design choice, so the only real decision is what to do during one, and it can be made differently for different operations (IEEE Computer 45(2), 2012). Refuse writes on both sides and stay consistent; accept them and stay available. GitHub's day of repair is the bill for the second option.

So consistency became a menu rather than a property. At the strict end is linearizability — every operation appears to take effect at a single instant between its start and its finish, which is to say the system successfully pretends to be one machine (Herlihy & Wing, ACM TOPLAS 12(3), 1990). At the loose end is eventual consistency: replicas may disagree now and will converge if you stop writing (Vogels, CACM 52(1), 2009). Between them lies a long spectrum, and choosing a point on it is the central architectural decision of any system spanning a building, let alone a planet.

One more move is available: buy "now" back with hardware. Google's Spanner equips its data centers with GPS receivers and atomic clocks, and its TrueTime interface reports not a timestamp but an interval — the uncertainty ε "varies from about 1 to 7 ms over each poll interval," roughly 4 ms most of the time (OSDI 2012). A transaction that must be globally ordered waits out the uncertainty before committing. It is the most literal illustration of the tower: a floor that could not assume a global clock bought one, in satellites, and sold the result upward as an ordinary database.

The oldest warning here is still the most useful. Around 1994 Peter Deutsch listed the false assumptions newcomers make — the network is reliable, latency is zero, bandwidth is infinite, the network is secure, topology doesn't change, there is one administrator, transport cost is zero — and James Gosling later added the eighth, that the network is homogeneous (Gosling). Each is a place where the abstraction of "one machine" leaks, and every large outage of the last thirty years is a receipt for one of them.

Connections

Below: chapter 09 supplies the messages and, crucially, their unreliability — this floor exists because that one cannot promise delivery. Chapter 05 owns concurrency within one machine, where locks work and failure is unambiguous; the gap between them is exactly what shared memory was buying. Chapter 08 supplies the guarantees traded away here. Above: chapter 07 pays the operational cost of every decision on this floor; chapter 11 replaces "machines may crash" with "machines may lie," a strictly harder problem; chapter 12 trains its models on clusters that are distributed systems in every respect above.

Open questions

Is consensus getting cheaper? Tight clock synchronization and fast data-center networks have narrowed the gap between the theory's worst case and the common one, and how much of the CAP trade is fundamental rather than an artifact of 2000-era networks is unsettled. Second: consistency models are precise but not intuitive, and most production bugs here come from engineers reasoning about a model they could define but not feel. Third, and largest: partial failure is the one thing no abstraction has ever fully hidden — every attempt to make a remote call look local has leaked. A flaw awaiting a fix, or the honest shape of the world showing through?

Go deeper

• Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM 21, no. 7 (1978): 558–565 — eight pages under everything above; award citation and links.
• Fischer, Lynch & Paterson, "Impossibility of Distributed Consensus with One Faulty Process," JACM 32, no. 2 (1985): 374–382 — the boundary of the possible; award citation.
• Maarten van Steen & Andrew S. Tanenbaum, Distributed Systems, 4th ed., 2023 — free PDF at distributed-systems.net. For the practitioner's view, Kleppmann & Riccomini, Designing Data-Intensive Applications, 2nd ed., O'Reilly, 2026.