Introduction and Overview: Distributed Systems

In one sentence

You think the hard part of distributed systems is having many machines. It is really that no observer can ever see "now". This chapter contains not a single algorithm; it hands you the assumption table that every algorithm in Part II shares — how reliable the link is, how trustworthy time is, and how nodes fail. Fill those three cells in wrong and consensus, replication and anti-entropy are all built on sand.

Glossary

Where it sits

Part I was about storage engines inside a single machine (B-Trees, LSM-Trees, transaction recovery). Part II steps outside, starting here. It follows Ch 7 and leads into Ch 9 failure detection, Ch 10 leader election, Ch 11 replication and consistency, Ch 12 anti-entropy and dissemination, and on to consensus in Ch 13–14. Which real systems does it map to? Everything with more than one replica — etcd / ZooKeeper, Cassandra / DynamoDB, Kafka, Spanner / CockroachDB. Their disagreements all live inside the coordinate system this chapter draws.

The problem it attacks

Single-machine programmers get three assumptions for free: a call returns, a read is current, a clock moves forward. Across machines all three die, and they die quietly — not with an error at first, but correctly under light load and wrongly under pressure. The book invokes Peter Deutsch's "fallacies of distributed computing" and names the first few: the network is reliable, latency is zero, bandwidth is infinite, topology doesn't change.

What happens if you ignore this? Three classic crashes. Ordering events by wall-clock time — two machines' now() can differ by milliseconds to tens of milliseconds between NTP corrections, so the later write is judged earlier and data is silently overwritten. Treating a timeout as death — the old leader was merely in an 8-second GC pause, a new leader is already elected, and two leaders accept writes at once (split brain). Blindly retrying on a network error — the first attempt actually succeeded, so the customer is charged twice. None of these is a coding bug; each is a wrongly filled assumption table.

The core, explained

1. Shared state: there is no such thing as a snapshot

The book's definition is plain: a distributed system is a set of independently executing processes that communicate only by passing messages. One consequence follows immediately — there is no "current global state". Each node holds only two things: its own local state, and whatever messages have arrived. No god's-eye view, no snapshot you can take in one shot.

So any claim about "what the system looks like right now" is only one node's guess at one moment, and it is stale by construction — stale by at least one one-way network delay. Deployed across continents, "latest" is at least 50 ms old. That is not a weak implementation; that is the speed of light.

2. The link ladder: unreliability is the floor, reliability is stacked on it

The most immediately useful section. It splits "the network" into three abstractions, each adding a guarantee:

• Fair-loss link — messages may be lost, duplicated or reordered, with exactly one guarantee: if you retransmit infinitely often, infinitely many get through. It promises nothing about any single message, only that it will not single you out forever.
• Stubborn link — fair-loss plus "resend forever, never stop". You now get eventual delivery, paid for with heavy duplication and no ordering.
• Perfect link — stubborn plus de-duplication by message ID. It offers three properties: validity (what is sent is eventually delivered), no duplication, and no creation (nothing arrives that was never sent).

The line to take away: a "reliable link" is not a property of the network; it is a floor you built on top of an unreliable one out of retries and bookkeeping. And you built it imperfectly — in practice "retransmit forever" is always "retry N times, then time out", so the perfect link is an ideal model, not a product you can buy.

3. Message order, and the truth about exactly-once

Ordering is a ladder too, four rungs from weak to strong: no order (arrive in any sequence) → FIFO order (messages from one sender are delivered in the order that sender emitted them) → causal order (causally related messages never invert; unrelated ones may arrive in any order) → total order (every node observes exactly the same sequence). Each rung costs more: FIFO needs one increasing counter per link; causal order needs causality metadata such as vector clocks; total order is essentially equivalent to running consensus, which is the job of Ch 13–14.

Delivery semantics have three rungs as well: at-most-once (fire and forget, may be lost), at-least-once (retry until acknowledged, may be duplicated), and exactly-once. That third one is the sentence to carry out of the chapter: at the link level, exactly-once is impossible. When a sender sees a failure or a timeout, it cannot separate "the message never arrived" from "it arrived, was processed, and the acknowledgement was lost" — the only status it can trust is success. What the industry calls exactly-once is always at-least-once plus idempotent de-duplication at the receiver: every message carries a unique ID, and the receiver keeps a table of IDs it has already processed.

4. Two Generals and FLP: two impossibility results

The Two Generals' Problem: two armies on opposite sides of a valley can only coordinate a simultaneous attack through messengers who cross enemy ground and may be captured. The result: no matter how many rounds of confirmation you exchange, the sender of the last message can never know whether it arrived. Over a link that may drop messages, two parties cannot reach certain agreement.

FLP impossibility (Fischer–Lynch–Paterson, 1985): in an asynchronous system, even if only one process may crash, there is no deterministic consensus algorithm that guarantees both termination and agreement. The root cause is the same old line — in an asynchronous system you cannot tell "crashed" from "merely slow".

The point is not "so consensus is impossible", it is that you must loosen one screw: add timing assumptions (use timeouts to treat the system as partially synchronous — the Raft and Paxos route), give up determinism (randomized consensus), or give up the promise of termination (never wrong, but possibly unable to elect a leader under adversarial scheduling). Real systems almost always pick the first: trade timeouts for liveness, and accept that timeouts lie sometimes.

5. System synchrony: three timing assumptions

The same algorithm yields different conclusions under different timing assumptions, so this cell must be filled first:

• Synchronous — message transfer and processing both have known upper bounds. Timeouts become a sound failure detector and algorithms get easy to write; real networks cannot supply that bound.
• Asynchronous — no timing bounds at all, clocks unusable. Closest to reality, with FLP standing in the doorway.
• Partially synchronous — bounded most of the time, occasionally not. This is where real systems live: Raft's election timeout and the φ-accrual detector of Ch 9 are both engineering inside this rung.

6. Failure models: how do you assume the other side breaks

The last cell is the shape of failure, cheap to expensive:

• Crash-stop — once down, never back. Easiest to reason about, least realistic.
• Crash-recovery — it comes back, carrying state that may be stale. This forces durable logs plus a catch-up mechanism.
• Omission fault — the process is alive but drops some sends or receives: packet loss under overload, long GC pauses. The nastiest kind, precisely because it still looks alive.
• Byzantine fault — arbitrary behavior, including lying and reporting different values to different nodes. The price is hard-coded: tolerating f crashes needs 2f+1 nodes; tolerating f Byzantine nodes needs 3f+1.

Database systems do not assume Byzantine faults by default — the machines sit in one organization's data center, and paying triple for the possibility of lying is not worth it. The scenarios that open that cell are blockchains and other mutually distrustful settings.

Key trade-offs

Table 1 · Delivery semantics: what you promise is what you pay for

Table 2 · Timing assumptions: get this cell wrong and the algorithm either cannot be written or cannot stay up

Table 3 · Failure models: the wilder the assumption, the more replicas it costs

Why it matters / in real systems

The value of this chapter is that it converts the platitude "distributed systems are hard" into three questions you can ask out loud in a design review — which rung of link are we assuming? which timing model? which failure model? The same applies in interviews: asked "how do you guarantee messages are neither lost nor duplicated", answering "we use the MQ's exactly-once" scores nothing. Answering "exactly-once is impossible at the link level, so we do at-least-once delivery plus idempotent de-duplication at the consumer, with a dedup table keyed on the business ID and retained for 7 days" is the answer of someone who has done it.

Pitfalls and disputes

• "It timed out, so it is dead" — wrong. A timeout only says "I heard nothing in that window". Treat it as a death certificate and you must accept occasional misjudgements; the real defense is not a better-tuned timeout but making the misjudgement harmless (fencing tokens, a leader that steps down when its lease expires).
• "Retries are always safe" — only when the operation is idempotent. A retry on a non-idempotent operation is a probabilistic double-execution device you installed yourself.
• "More machines mean more fault tolerance" — even numbers do not pay. Four nodes tolerate exactly what three do: one failure. The extra node only adds coordination cost and a way to deadlock during a partition.
• "CAP says you must choose between C and A" — over-propagated. Brewer's own framing is that you only forfeit consistency or availability during an actual partition; the rest of the time you can have both.
• "This is all theory, it doesn't matter in engineering" — the counterexample is above. Dataflow's "Deadline Exceeded is ambiguous" is the Two Generals' Problem showing up in one RPC status code.
• The chapter's own limits. It is a map of terms and models — clean, but also dry: the engineering that actually makes partial synchrony work (leases, hybrid logical clocks, fencing tokens) is largely left undiscussed, waiting for later chapters or other books.

Takeaways