The Trouble with Distributed Systems

Faults and partial failures

Fullscreen

A single computer is mostly deterministic, it presents an idealized model where the same operation always gives the same result, and a serious internal fault usually crashes it entirely (we prefer a crash to a wrong result). Across a network, faults are frequent and nondeterministic: an operation involving other nodes may work, fail, or hang unpredictably. Tolerating partial failure is what lets us do rolling upgrades and outlast single-node systems, but first you must understand the faults. Suspicion, pessimism, and paranoia pay off, and you should deliberately inject faults in testing.

---

Unreliable Networks

Shared-nothing systems communicate only over an asynchronous packet network (Ethernet, the internet) with no guarantee a packet arrives, or when.

Fullscreen

If you get no reply, you cannot tell why, and even after a timeout, your request might still be queued and get delivered later.

The limitations of TCP

TCP provides "reliable" per-connection delivery (retransmits drops, reorders, checksums, congestion/flow control), but it does not save you from network unreliability:

• It can't tell whether the outbound packet or the ack was lost; eventually it gives up and errors.
• Dedup/retransmit apply only within one connection, reconnecting and retrying can duplicate data.
• A connection closing with an error tells you nothing about how much the remote app processed. Even a kernel-level ack doesn't mean the app handled it, you need a positive response from the application itself.

Network faults in practice

Networks are surprisingly unreliable even in one company's datacenter:

• A study found ~12 network faults/month (half disconnect a machine, half a whole rack).
• Redundant gear doesn't help as much as expected because it doesn't guard against human error (misconfigured switches), a major cause of outages.
• Fiber cuts blamed on cows, beavers, sharks, and human misconfiguration/sabotage; delays of minutes observed; asymmetric faults happen (A↔B and B↔C work, but A↔C doesn't; an interface that drops inbound but sends outbound).
• A brief interruption can have long-lasting repercussions. So your software must handle faults, though "handle" can mean simply showing users an error, as long as you know how it reacts and that it recovers.

A network partition (netsplit) is just one part of the network being cut off, not fundamentally different from other interruptions, and unrelated to sharding/partitioning (Ch. 7).

Fault detection

Sometimes you get explicit signals: a TCP RST/FIN if no process is listening, a crash-notification script, switch management interfaces, or an ICMP Destination Unreachable. But you can't rely on any of them, generally you must assume no response, retry, and declare dead after a timeout. This balances false positives (live node wrongly suspected) against false negatives (slow to detect real death).

Timeouts and unbounded delays

Fullscreen

In a hypothetical network with max delay d and max handling time r, 2d + r would be a sound timeout, but real networks have unbounded delay and servers can't bound handling time. Variable delay comes mostly from queueing: at switches (network congestion → dropped packets), at the destination CPU/threads, during VM pauses, and at the TCP sender. Queues balloon near max capacity, and in clouds a noisy neighbor adds variability. (UDP drops flow control/retransmission, good when delayed data is worthless, e.g. VoIP.)

Synchronous vs asynchronous networks

Fullscreen

A telephone circuit reserves fixed bandwidth → bounded delay. The internet uses packet switching, optimized for bursty traffic (we want files/pages done as fast as possible, with no fixed bandwidth need). Variable delay is therefore not a law of nature but a cost/benefit trade-off: static partitioning gives latency guarantees but wastes capacity; dynamic sharing is cheaper but variable. QoS / L4S could emulate bounded delay but aren't enabled in multitenant clouds or the public internet, so assume congestion and unbounded delays, and pick timeouts experimentally.

---

Unreliable Clocks

Each machine has its own quartz clock; NTP syncs them (ultimately from GPS/atomic sources). Two kinds of clock, for two different jobs:

Fullscreen

Clock sync and accuracy problems

• Quartz drift (~200 ppm at Google → ms of error between syncs); a clock too far off may be forcibly reset (jumps backward/forward).
• NTP accuracy is limited by network delay (~35 ms minimum over the internet, spikes to ~1 s); misconfigured/firewalled NTP goes unnoticed; some NTP servers are simply wrong.
• Leap seconds (a 59- or 61-second minute) have crashed big systems; best handled by smearing (gone after 2035).
• VMs virtualize the clock, a paused VM sees time jump forward; an in-VM NTP client misjudges accuracy.
• Untrusted devices (phones, embedded) can't be trusted at all. High accuracy (MiFID II's 100 µs) needs GPS/atomic clocks + PTP + careful monitoring.

The danger: a bad clock fails silently. A broken CPU or NIC crashes loudly; a drifting clock just produces subtle, silent data loss. Monitor clock offsets and evict nodes that drift too far.

Relying on synced clocks is dangerous

Timestamps for ordering events is the classic trap:

Fullscreen

With last-write-wins, a node with a lagging clock can't overwrite a faster node's values until the skew elapses → arbitrary silent data loss; LWW also can't tell sequential from truly concurrent writes (need version vectors), and equal timestamps need a tiebreaker. NTP can never be accurate enough (its error exceeds network delay), so use logical clocks (counters tracking ordering, not elapsed time) instead of physical clocks for ordering.

Clock readings as confidence intervals: a reading isn't a point but a range [earliest, latest]. Most APIs hide this, but Google Spanner's TrueTime and Amazon ClockBound expose it. Global snapshots: Spanner uses TrueTime for cross-datacenter snapshot isolation, if two intervals don't overlap, their order is certain, so Spanner deliberately waits out the confidence interval before committing (GPS/atomic clocks keep the interval ~7 ms, minimizing the wait). The interval, not the atomic clock, is the essential part.

---

Process Pauses

A leader holding a lease (a lock with a timeout) might check "is my lease still valid?" and then get paused right before acting:

Fullscreen

A thread can pause for an unbounded time at any point: GC stop-the-world (historically minutes), VM suspend / live migration, OS context switches / steal time, synchronous disk I/O (even surprise class-loading), page faults / swapping / thrashing, or a SIGSTOP. During the pause the world moves on and may declare the node dead. Single-machine thread-safety tools (mutexes, etc.) don't translate, there's no shared memory, only messages over an unreliable network.

• Response-time guarantees: hard real-time systems (airbags, aircraft) meet deadlines via an RTOS, bounded library/GC behavior, and heavy testing, expensive, lower throughput, only for safety-critical embedded use. Not economical for servers.
• Limiting GC impact: tuned collectors (CMS, G1, ZGC, Shenandoah) cut pauses to ~ms; non-GC languages (Rust, Swift, Mojo); object pools / off-heap; treat GC like a planned outage (drain traffic, then collect); periodic restarts before long-lived objects accumulate.

---

Knowledge, Truth, and Lies

A node can't know another node's state, only infer from messages received (or not). Network problems can't be distinguished from node problems. We cope by stating a system model (assumptions) and designing algorithms provably correct within it.

The majority rules

Three nightmares: an asymmetric fault (a healthy node whose outbound messages are dropped is wrongly buried alive); a node that realizes it's cut off but can't do anything; and a paused node that wakes to find it was declared dead. The moral: a node can't trust its own judgment, and the system can't depend on any single node. Use a quorum (voting): decisions need a minimum number of votes. A majority quorum (> half) is safe (only one majority can exist, so no conflicting decisions) and tolerant (3 nodes tolerate 1 failure; 5 tolerate 2). A node declared dead by a quorum must step down, even if it feels alive.

Distributed locks and leases

Leases enforce "only one of X" (one leader per shard, one writer per resource, one processor per file). But two nodes can simultaneously believe they hold the lease:

• Process-pause bug (HBase-real): the leaseholder pauses past expiry, another acquires the lease, the paused one wakes and keeps writing → split brain, corrupted file.
• Delayed-request bug: client 1 sends a write, then its lease expires (or it crashes); the delayed packet arrives after client 2 took over → same corruption.

Fencing off zombies (a zombie = a former leaseholder that doesn't yet know it lost the lease):

Fullscreen

• STONITH (shoot the other node in the head) is insufficient, it doesn't stop delayed packets, nodes could shut each other down, and corruption may already have happened.
• Fencing tokens are the robust fix: a monotonically increasing number issued with each lease; storage rejects any write with a lower token. Same idea as Chubby's sequencers, Kafka's epoch, Paxos's ballot / Raft's term, ZooKeeper's zxid, etcd's revision; or use conditional write / CAS (S3 conditional writes, Azure conditional headers, GCS preconditions).
• Fencing with multiple replicas: put the token in the high bits of the timestamp so a new leaseholder's writes always outrank a zombie's, even in a leaderless LWW store.

Byzantine faults

Fencing handles a node acting in honest error, but not a node that lies (e.g., forges a token or casts contradictory votes). A node sending arbitrary/malicious responses is a Byzantine fault; agreeing despite traitors is the Byzantine Generals Problem. Byzantine fault tolerance matters for aerospace (radiation-corrupted memory) and blockchains (mutually untrusting parties), but in datacenters we assume nodes are unreliable but honest: BFT is expensive, and if all nodes run the same buggy/compromised software, BFT doesn't help anyway. Traditional defenses (authn, access control, encryption, firewalls, input validation) are what protect against attackers. Still, cheap weak-lying guards are worth it: application-level checksums, input sanitization, and multiple NTP servers (outlier detection).

---

System Model and Reality

Algorithms assume a system model abstracting expected faults.

Fullscreen

The partially synchronous model with crash-recovery faults is generally the most useful for real systems. Degraded/limping/gray/fail-slow nodes (responding but uselessly slow) are often harder to handle than cleanly-failed ones.

Correctness, safety, and liveness

Define correctness via properties. For fencing-token generation: uniqueness (no two requests get the same token), monotonic sequence (if x completed before y began, token(x) < token(y)), and availability (a non-crashing requester eventually gets a response).

Fullscreen

Distributed algorithms typically require safety to hold in all situations (even if every node crashes, never return a wrong result), while liveness may carry caveats (e.g., respond if a majority is up and the network eventually recovers, exactly the partially synchronous assumption).

Mapping to reality: models are simplifications. Crash-recovery assumes stable storage survives, but disks get corrupted/wiped, firmware loses drives, and a node with "amnesia" breaks quorum correctness. Real implementations still need code for "impossible" cases (even if it's just log-and-exit for a human to clean up). Models are still invaluable for distilling complexity into something you can reason about.

---

Formal Methods and Randomized Testing

The state space is huge, so combine theory + empirical testing:

• Model checking, specify the algorithm in TLA+, Gallina, or FizzBee; the checker systematically explores states to verify invariants. It runs a model, not your code (risk: model and implementation drift apart), and usually bounds the search. Used by CockroachDB, TiDB, Kafka; TLA+ found a data-loss bug in viewstamped replication.
• Fault injection, inject real faults (kill/pause processes, unmount disks, firewall connections) into a running system. Netflix's Chaos Monkey popularized doing this in production (chaos engineering); Jepsen is a framework that has found many critical bugs.
• Deterministic simulation testing (DST), explores the state space like a model checker but runs your actual code, with network/IO/clocks replaced by controllable mocks → reproducible (replay the exact failing order) and faster than wall-clock. Three approaches: application-level (FoundationDB's Flow, TigerBeetle), runtime-level (FrostDB patching Go, Rust's MadSim), machine-level (Antithesis's deterministic hypervisor).

The power of determinism. Nondeterminism (concurrency, delays, pauses, clock jumps, crashes) is the root of every distributed-systems problem; making things deterministic simplifies enormously. It recurs across the book: event sourcing (replay a log to rebuild views), workflow engines (durable execution), and state machine replication (statement-based replication, serial stored-procedure execution). But full determinism is hard, hash-table iteration order and resource limits can still be nondeterministic.

---

Real-world examples and analogies

• Partial failure, a phone tree where some people don't pass the message. On one computer the message either goes out or it doesn't. In a distributed system it's a phone tree: some links pass it, some silently drop it, and you can't tell which, you may never know if your message got through.
• No-response ambiguity, texting someone with no reply. Did they not get it? Are they ignoring you? Did they reply and it got lost? You genuinely cannot distinguish, a timeout is just you giving up, not knowledge of what happened.
• TCP's limit, a signed delivery receipt for a package nobody opened. The courier's "delivered" scan (kernel ack) doesn't mean the recipient read the letter (the app processed it). You need them to write back.
• Timeout tuning, declaring a quiet coworker "gone." Wait 5 seconds and you'll wrongly assume a thinking colleague has left; wait an hour and you're slow to notice real departures. Worse, reassigning their work when they were merely slow can pile onto an already-overloaded team (cascading failure).
• Circuit vs packet switching, a reserved lane vs a shared highway. A phone circuit is a private lane with guaranteed travel time; the internet is a shared highway that's cheaper and busier but jams unpredictably.
• Time-of-day vs monotonic, a wall clock vs a stopwatch. Use the wall clock to say when something happened (but it can be reset backward); use the stopwatch to measure how long something took (it only ever counts up).
• LWW clock skew, two referees with mis-set watches. The later goal gets an earlier timestamp because that referee's watch runs slow, so the scoring system "corrects" by deleting the real goal. Logical clocks (a simple counter) avoid this.
• Confidence interval, "sometime between 10:03 and 10:05." An honest clock admits a range, not a false-precision instant. Spanner waits out that range so it can be sure event B really came after event A.
• Process pause + fencing, a security guard who naps past shift change. A guard with an expired badge wakes and keeps unlocking doors. The fix isn't trusting badges to expire on time, it's a door that only accepts the highest badge number ever issued, so the napping guard's old badge is refused.
• Byzantine fault, a traitor among the generals. Most generals send honest messages, but a traitor sends contradictory ones to different peers. Worth defending against in space and on blockchains; in your datacenter you trust your own nodes and just checksum against accidental corruption.
• Safety vs liveness, "never convict the innocent" vs "eventually hold the trial." Safety (no wrongful conviction) must hold always; liveness (the trial happens eventually) can be delayed by circumstances but is still the goal.

---

Cheat-sheet flashcards

Cover the answer and recall it.

• What defines a distributed system's difficulty? → Partial failure (nondeterministic) and not knowing if an operation succeeded.
• Why do single computers crash rather than return wrong results? → Wrong results are confusing; a clean crash is preferred.
• What kind of network is the internet/datacenter? → Asynchronous packet network (no delivery/timing guarantees).
• Six ways a request/response can fail? → Request lost/queued, node crashed/paused, response lost/delayed.
• Only tool for detecting no response? → A timeout.
• Does TCP make networks reliable enough to ignore faults? → No, it can't say what the remote app processed; need an app-level positive response.
• How often do network faults occur (one study)? → ~12 per month in a medium datacenter.
• Why doesn't redundant network gear fix things? → It doesn't guard against human error (misconfiguration).
• What is an asymmetric network fault? → Messages flow one direction but not the other.
• Is a network partition related to sharding? → No, different meaning entirely.
• Trade-off in setting a timeout? → Too short = false positives (premature death); too long = slow detection.
• What can premature death cause? → Duplicate actions and cascading failure.
• Main cause of variable network delay? → Queueing (congestion, CPU/thread, VM, TCP sender).
• Why does the internet use packet switching? → Optimized for bursty traffic and better utilization.
• Is variable delay a law of nature? → No, it's a cost/benefit trade-off (utilization vs guarantees).
• Time-of-day clock, use and hazard? → Points in time; can jump backward (unsuitable for durations).
• Monotonic clock, use and limit? → Durations; meaningless across machines.
• Why is a bad clock dangerous? → It fails silently, causing subtle data loss.
• Why is LWW by timestamp risky? → Clock skew silently drops causally-later writes.
• Physical vs logical clocks? → Measure elapsed time vs only event ordering.
• What is a clock confidence interval? → [earliest, latest] range; exposed by TrueTime / ClockBound.
• How does Spanner order transactions safely? → Waits out the confidence interval so intervals don't overlap.
• Six causes of process pauses? → GC, VM suspend/migration, context switch/steal time, disk I/O, page faults/swapping, SIGSTOP.
• What is a hard real-time system? → One that must meet deadlines (RTOS); expensive, lower throughput.
• Ways to limit GC impact? → Tuned/no-GC languages, object pools, treat GC as planned outage, periodic restarts.
• Why can't a node trust its own judgment? → It may be paused or partitioned without knowing.
• What is a quorum and why is a majority safe? → Voting among nodes; only one majority can exist (no conflicting decisions).
• What is split brain via a lease? → Two nodes both believing they hold the lease.
• Why is STONITH insufficient? → Doesn't stop delayed packets; nodes can kill each other; may be too late.
• What is a fencing token? → A monotonically increasing number; storage rejects lower tokens.
• Other names for fencing tokens? → Sequencers (Chubby), epoch (Kafka), ballot (Paxos), term (Raft), zxid (ZooKeeper).
• What is a Byzantine fault? → A node lying / sending arbitrary or malicious responses.
• When does Byzantine fault tolerance matter? → Aerospace and blockchains (mutually untrusting parties).
• Why is BFT usually unnecessary in datacenters? → Nodes are trusted; same software means a bug/compromise hits all.
• Three weak-lying guards? → App-level checksums, input sanitization, multiple NTP servers.
• Three timing models? → Synchronous, partially synchronous (most realistic), asynchronous.
• Four node-failure models? → Crash-stop, crash-recovery (most useful), degraded/fail-slow, Byzantine.
• Safety vs liveness? → "Nothing bad happens" (permanent, always holds) vs "something good eventually happens" (caveats allowed).
• Is eventual consistency safety or liveness? → Liveness.
• Three randomized-testing techniques? → Model checking (TLA+), fault injection (Jepsen/Chaos Monkey), deterministic simulation testing.
• What makes DST different from model checking? → It runs your actual code, not a model, and is replayable.

---

Common interview questions

1. What is partial failure, and why does it make distributed systems hard? (Nondeterministic breakage; you can't tell if an operation succeeded.)
2. If you send a request and get no response, what could have happened? (Six modes; indistinguishable; only a timeout helps.)
3. TCP is "reliable", so why must apps still handle network faults? (Per-connection only; can't confirm app processing; reconnects can duplicate.)
4. How do you set a timeout for failure detection? (No correct value; false-positive vs false-negative; measure experimentally; Phi Accrual.)
5. Why do packet networks have unbounded delay, and is that avoidable? (Queueing; cost/benefit vs circuit switching; QoS not enabled in clouds.)
6. Time-of-day vs monotonic clocks, when do you use each? (Points in time vs durations; jumps vs always-forward.)
7. Why is last-write-wins by wall-clock timestamp dangerous? (Clock skew silently drops writes; use logical clocks / version vectors.)
8. How does Spanner use clock uncertainty for correctness? (TrueTime intervals; commit-wait so intervals don't overlap.)
9. Why can a process pause break a lease/lock, and how do fencing tokens fix it? (Pause past expiry → zombie/split brain; storage rejects lower tokens.)
10. What is a Byzantine fault, and when do you need BFT? (Nodes lying; aerospace/blockchain; usually unnecessary/costly in datacenters.)
11. Explain the common system models (timing and node failure). (Synchronous/partially/asynchronous; crash-stop/recovery/degraded/Byzantine.)
12. What's the difference between safety and liveness, and why does it matter? (Permanent vs eventual; safety must always hold, liveness can have caveats.)

---

Key terms glossary

---

Forward links (where these ideas return)

• Consensus, linearizability, leader election, lock/coordination services → Chapter 10
• Fencing tokens, ballot/term numbers, shared logs, ID generators / logical clocks → Chapter 10
• Exactly-once / idempotence (handling duplicate actions after false death) → Chapter 12
• LWW, version vectors, conflict resolution → Chapter 6
• Gray failures and reliability/fault tolerance → Chapter 2
• Determinism: event sourcing, durable execution, state machine replication → Chapters 3, 5, 10