A single computer is a well-behaved deterministic machine: an operation works or fails, and hardware faults usually take the whole thing down rather than leaving it half-working. A distributed system is different in kind. Nodes fail independently, the network drops and delays messages arbitrarily, clocks disagree, and a process can freeze for a minute without noticing. The defining property is partial failure, and worse, nondeterministic partial failure: often you cannot even tell whether something failed.

This is the most pessimistic chapter in the book and the foundation for the consistency and consensus material that follows. For interviews it supplies the vocabulary for timeouts, leader election, distributed locks and ordering: whenever a design relies on "the leader knows it is the leader" or "the timestamp says which write came first", this chapter explains why that is dangerous and what to do instead.

In one minute

• Parts of a distributed system fail while others work, and a dead node is indistinguishable from a slow one. Build fault tolerance in from the start.
• Networks are asynchronous packet networks: messages may be lost, delayed or reordered, and the sender learns nothing without a reply. Timeouts are the only failure detector, and their value trades slow detection against false positives.
• Latency is unbounded because of queueing at switches, operating systems, virtual machines and TCP. Circuit-switched networks bound latency but waste capacity; datacenters chose utilisation.
• Machines have a time-of-day clock (NTP-synchronised, may jump) and a monotonic clock (for durations, never jumps). Never use the time-of-day clock for elapsed time or to order events across nodes.
• Last-write-wins with wall-clock timestamps silently drops causally later writes. Logical clocks are the right ordering tool. Spanner's TrueTime makes timestamps safe only by exposing uncertainty intervals and waiting them out.
• A process can pause at any instant for seconds or minutes (GC, VM migration, I/O, swapping, SIGSTOP). "I still hold the lease" may be stale by the next line.
• A node cannot trust its own judgement; the majority decides. Protect resources from a confused ex-leader with fencing tokens that the resource verifies.
• Reason with an explicit system model: partially synchronous timing with crash-recovery nodes is the realistic default. Safety must always hold; liveness may hold only eventually.

Faults and partial failures

Software on one computer is predictable: working hardware gives the same result every time, and broken hardware (corrupt memory, a loose connector) usually causes total failure, a kernel panic rather than a subtly wrong answer. Networked software loses this property: some parts may be broken in unpredictable ways while others work fine, and you may not know whether a request succeeded.

Two philosophies bracket the design space. High-performance computing treats partial failure as total failure: a simulation checkpoints to durable storage and, when any node fails, the whole job restarts from the checkpoint, which is fine for offline batch work. Cloud computing cannot do that: commodity hardware fails more often, services must stay online with low latency, nodes talk over IP networks with worse latency variance than HPC interconnects, and in a system of thousands of nodes something is always broken. The stance becomes: build a reliable system from unreliable components, as TCP does over IP, accepting that the abstraction is imperfect (TCP cannot hide latency). Fault handling must be designed in and tested, by deliberately triggering faults (Netflix's Chaos Monkey) and checking the response.

Unreliable networks

The systems in this book are shared-nothing: machines communicate only by messages over a network. The internet and datacenter Ethernet are asynchronous packet networks: a node sends a packet with no guarantee of when, or whether, it arrives.

If you get no response, any of these happened: the request was lost; it is queued behind overload; the remote node crashed; the remote node is paused (a long GC) and will resume; the response was lost; or the response is merely delayed. The sender cannot tell. The only option is a timeout: give up after some time, knowing the request may nevertheless have been processed.

Network faults in practice

A study of a medium-sized datacenter found about 12 network faults per month, half disconnecting a single machine and half a whole rack. Redundancy helps less than hoped because human error (misconfigured switches) is the main cause. Public clouds glitch regularly; sharks bite undersea cables; interfaces fail asymmetrically, delivering inbound but not outbound packets. When one part of the network is cut off from the rest, that is a network partition or netsplit (the book says "network fault" to avoid confusion with Chapter 6). You need not tolerate every fault gracefully, but you must know how your software reacts: an error message is acceptable; a hang, deadlock or silent data loss is not.

Detecting faults

Load balancers must stop sending to dead nodes; single-leader databases must fail over. Some feedback exists: a closed port yields RST or FIN; a supervisor script can report a crashed process (HBase does this); a switch's management interface may report link failure; a router may send ICMP Destination Unreachable. None is reliable, because the fault may be in the component that would report it. In general you must assume no response at all, retry a few times, and ultimately let a timeout declare the node dead.

Timeouts and unbounded delays

A long timeout means users wait through a long outage before failover. A short one detects faults fast but risks declaring a slow node dead, which is dangerous: if the node is alive and mid-action (sending an email), a replacement may repeat the action, and in an overloaded cluster shifting a slow node's load onto struggling peers causes cascading failure. In a fictional network with maximum packet delay d and maximum processing time r, a timeout of 2d + r would be safe; real networks have unbounded delays and servers no guaranteed processing time, so no such constant exists.

Network congestion and queueing

Delay variability comes mostly from queueing: several senders target one destination and the switch queues (and, when full, drops) packets; the destination's CPUs are all busy and the OS queues the request; a virtual machine is paused while another VM uses the core and the hypervisor queues its data; TCP flow control queues data at the sender; TCP retransmits after a timeout, so the application sees the delay. Noisy neighbours in multi-tenant clouds and batch jobs saturating links make it worse. Timeouts are therefore best chosen experimentally, from the measured round-trip distribution over many machines and a long period, or adaptively: phi-accrual failure detectors (Akka, Cassandra) and TCP's own retransmission timeout track variability continuously.

Synchronous versus asynchronous networks

Why not guarantee bounded delay, as the telephone network does? A call establishes a circuit with reserved bandwidth along the whole route; nothing queues, so latency has a fixed maximum: a synchronous network. Datacenter and internet traffic is packet-switched because it is bursty: a web request or file transfer has no fixed bandwidth need, it just wants to finish quickly, and a circuit would waste capacity when idle and be too slow when busy. Hybrids exist (ATM, InfiniBand with link-layer flow control, quality-of-service and admission control), but not in multi-tenant datacenters or the public internet. Bounded latency and high utilisation are in fundamental tension, and the internet chose utilisation.

Unreliable clocks

Applications use clocks for durations (did the request time out? what is p99 latency?) and for points in time (when was this published? when does the cache entry expire?). Each machine has its own quartz clock that drifts, and communication is not instantaneous. The Network Time Protocol (NTP) adjusts clocks toward servers that use GPS or atomic references, but synchronisation is far from perfect.

Monotonic versus time-of-day clocks

Property	Time-of-day clock	Monotonic clock
Returns	Wall-clock time since the epoch	A counter whose absolute value is meaningless
APIs	clock_gettime(CLOCK_REALTIME), System.currentTimeMillis()	clock_gettime(CLOCK_MONOTONIC), System.nanoTime()
Can jump backwards	Yes, when NTP steps it or an operator resets it	Never
NTP influence	Jumps or slews to the reference	May only adjust the rate (slew up to about 0.05 percent)
Comparable across machines	Roughly, within sync error	No
Use for	Timestamps, calendar scheduling	Timeouts, elapsed time, latency

Time-of-day clocks typically ignore leap seconds, another reason they are unsuitable for durations.

Clock synchronisation and accuracy

A quartz clock drifts: Google assumes 200 parts per million, which is 6 ms of drift per 30-second sync interval, or 17 seconds per day unsynchronised. A clock too far from its NTP server may refuse to sync or be forcibly reset, so applications see time jump. A misconfigured firewall can block NTP unnoticed for a long time. NTP accuracy is bounded by network delay (35 ms is achievable, with spikes over a second). NTP servers can be wrong by hours or years, so clients should query several and reject outliers. Leap seconds create 59- or 61-second minutes and have crashed systems (the 2012 Linux leap-second bug); the fix is to smear the adjustment over a day. Virtual machines see time jump after being paused, and devices you do not control may have deliberately wrong clocks.

High accuracy is possible with GPS receivers, the Precision Time Protocol and careful monitoring; the European MiFID II regulation requires high-frequency trading clocks within 100 microseconds of UTC. It is hard, and it does not happen by default.

Relying on synchronised clocks

A broken clock is silent: software keeps running with a wrong time rather than crashing. Any software depending on synchronised clocks must monitor offsets across machines and evict nodes whose clocks drift too far.

Timestamps for ordering events. Suppose a multi-leader database resolves conflicts by last write wins on wall-clock timestamps. Node 1 writes x = 1 at 42.004; node 3, whose clock is 3 ms behind, then writes x = 2 at 42.003. Node 2 keeps the "later" x = 1 and silently discards x = 2, which was causally later. Clients saw both writes succeed; one vanished. LWW cannot distinguish sequential from concurrent writes; two nodes can produce identical millisecond timestamps, needing an arbitrary tiebreaker; and NTP error (tens of milliseconds) exceeds the typical gap between causally related writes. The right ordering tool is a logical clock (an incrementing counter, or Chapter 5's version vectors), which orders by causality rather than by physical time. Physical clocks are good for durations and human-readable labels, bad for ordering.

Clock readings are confidence intervals. A clock reading is a range, not a point: a quartz clock 30 seconds after an NTP sync at 200 ppm drift is uncertain by about 6 ms plus the NTP round trip, a GPS-disciplined clock by microseconds. Most APIs hide this and return one number. Google's TrueTime API in Spanner returns [earliest, latest], bounds the true time is guaranteed to lie between.

Synchronised clocks for global snapshots. Snapshot isolation (Chapter 7) needs monotonically increasing transaction IDs, which are a bottleneck across a distributed database. Could timestamps serve instead? Only if uncertainty is respected. In Spanner, if two transactions' TrueTime intervals do not overlap their order is unambiguous; if they overlap, it is unknown. To ensure any later-committing transaction gets a later non-overlapping timestamp, Spanner deliberately waits the length of the confidence interval before committing (commit-wait). Google keeps that wait short, around 7 ms, by deploying a GPS receiver or atomic clock in each datacenter. No other mainstream database relies on this; it is an engineering achievement rather than a generally available technique.

Process pauses

Consider a single-leader database whose leader holds a lease, a lock with an expiry it must renew. Before processing each request it checks "do I still hold the lease, with a margin of ten seconds?" First problem: it compares an expiry set by another machine against its local clock, so it relies on synchronised clocks. Second, and worse: between the check and the processing, the thread may pause. If it pauses fifteen seconds, the lease expires, another node takes over, and this node resumes and processes the request believing it is still leader.

Such pauses are real: stop-the-world garbage collection that occasionally lasts minutes; a virtual machine suspended or live-migrated; a laptop lid closing; the OS context-switching or a hypervisor stealing the CPU; synchronous disk I/O stalling (even a Java class loader lazily loading a class, or a network filesystem); swapping that thrashes so hard progress stops, which is why many servers disable paging; a SIGSTOP (an operator's Ctrl-Z) until SIGCONT. A node must assume execution can pause for a significant time at any point, even mid-function, while the rest of the world moves on and may declare it dead.

Response-time guarantees do exist in hard real-time systems (aircraft, rockets, airbags): a real-time OS with guaranteed scheduling, documented worst-case execution times, restricted dynamic allocation and enormous testing, at the price of lower throughput and much higher cost. That is not applicable to server-side data processing. Two mitigations limit garbage collection pauses: treat them as brief planned outages, with the runtime warning the application so the node stops taking requests and others cover; or collect only short-lived objects and restart processes periodically (rolling restarts) before a full GC is needed. Both reduce the effect; neither eliminates pauses.

Knowledge, truth and lies

A node knows nothing for certain about other nodes; it can only guess from messages it receives or fails to receive. If a node does not respond there is no way to know why. The engineering consequence is that we state assumptions explicitly (the system model) and design algorithms that are provably correct under them.

The truth is defined by the majority

A node whose outgoing messages are dropped is declared dead by the others while it keeps working, baffled that nobody answers. A node that pauses for a minute of GC resumes with no idea it was declared dead and replaced. A node therefore cannot trust its own judgement about its status. Distributed algorithms rely on a quorum, a vote among nodes with decisions made by a strict majority of n: if a majority declares a node dead, it is dead and must step down even if it disagrees. Two majorities of one set always share a node, so two conflicting decisions cannot both pass. Chapter 9's consensus algorithms build on this.

The leader and the lock

Systems often need exactly one of something: one leader per partition (no split brain), one holder of a lock on a resource, one user per username. A node may believe it is the chosen one while a quorum has already replaced it, and if it keeps acting the system does something wrong. A real HBase bug: a client acquires a lease to write an HDFS file, pauses for a long GC, its lease expires, a second client acquires the lease and writes; the first client wakes and, believing it still holds the lease, writes too. The file is corrupted.

Fencing tokens

The fix is fencing: every time the lock service grants a lock or lease it also returns a fencing token, a number that increases with every grant. Clients include the token with every write, and the storage service rejects any write whose token is lower than one it has already seen.

With ZooKeeper as lock service, the transaction ID zxid or node version cversion serves as the token, since both increase monotonically. The vital point is that the resource itself checks tokens: it is unwise for a service to assume its clients will always behave well. A lock that depends on the client's own sense of time is not a lock, and server-side checking also protects against buggy clients.

Byzantine faults

Fencing handles nodes that are mistaken. A node that deliberately lies (a forged token, a false claim about messages received) is a Byzantine fault, after Lamport's Byzantine Generals Problem of generals agreeing on a plan while some are traitors. A system is Byzantine fault-tolerant if it works correctly despite malfunctioning or malicious nodes. This matters in aerospace (radiation flips bits, so flight computers vote) and in multi-organisation systems where participants may cheat (blockchains agree on transactions without a trusted authority). Datacenter systems usually assume no Byzantine faults: one organisation controls all nodes, radiation is low, and an attacker who compromises one node can usually compromise all, so the costly protocols buy little. Weak lies still occur without malice: corrupt packets slipping past TCP checksums (add application-level checksums), invalid input (validate it), wrong NTP servers (query several, reject outliers).

System model and reality

Algorithms are written for an abstract system model stating which faults may occur, along two dimensions.

Timing and node-failure assumptions

Timing model	Assumption	Realism
Synchronous	Bounded network delay, pauses and clock error	Unrealistic
Partially synchronous	Synchronous most of the time, occasionally exceeding the bounds	Realistic for datacenters
Asynchronous	No timing assumptions, no clocks, no timeouts	Very restrictive; few algorithms possible

Failure model	Assumption
Crash-stop	A node fails only by crashing and never returns
Crash-recovery	A node may crash and later return; stable storage survives, memory is lost
Byzantine	Nodes may do anything, including deceiving others

The most useful model for real systems is partially synchronous with crash-recovery, which most algorithms in Chapter 9 assume.

Correctness, safety and liveness

Correctness is defined by properties. A fencing-token generator should satisfy uniqueness (no two requests get the same token), monotonic sequence (if request x completed before y began, x's token is lower) and availability (a non-crashing requester eventually gets a token). An algorithm is correct in a model if it satisfies its properties in every situation the model allows.

These properties split into two classes. A safety property says nothing bad happens (uniqueness, monotonic sequence): if violated, there is a specific moment of violation and the damage cannot be undone. A liveness property says something good eventually happens (availability): it may not hold yet, but there is always hope. The word "eventually" marks liveness; "eventual consistency" is one. The rule: safety must hold in all circumstances, even if every node crashes or the network drops everything; liveness may carry caveats, such as "a response arrives if a majority of nodes are up and the network eventually recovers". The partially synchronous model's "eventually returns to synchronous" is exactly such a caveat.

Mapping models to the real world

Models are abstractions. Crash-recovery assumes stable storage survives, but disks corrupt and firmware has bugs; a quorum algorithm assumes a node remembers what it acknowledged, which a disk failure breaks. Implementations must handle "impossible" cases, if only by logging and asking a human. The value of theory is not perfect description of reality but precise reasoning that exposes the assumptions correctness rests on.

Design trade-offs

Decision	Option A	Option B	Guidance
Timeout length	Short: fast detection, false positives, duplicate actions, cascading failure	Long: slow detection, users wait	Measure the latency distribution; use adaptive detectors; make actions idempotent so false positives are survivable
Ordering events	Wall-clock timestamps (LWW loses writes)	Logical clocks or version vectors	Logical clocks; wall clocks only with explicit uncertainty (TrueTime)
Measuring durations	Time-of-day clock	Monotonic clock	Always monotonic
Protecting a leased resource	Trust the holder's lease check	Fencing tokens verified by the resource	Fencing tokens, always
Fault model	Crash-recovery	Byzantine	Crash-recovery inside one organisation; Byzantine only when participants may cheat

Interview angle

• A request times out. What are the explanations, and what can the client conclude? Lost request, queued request, crashed or paused node, lost or delayed response. The client learns nothing about whether the operation executed, so operations should be idempotent or deduplicated before retrying, and a timeout means "unknown", not "failed".

• How do you choose a timeout for failure detection? No constant is safe because delays are unbounded. Measure the round-trip distribution across machines and time, set from a high percentile, and prefer adaptive phi-accrual detectors. Weigh slow detection against duplicate actions and cascading failures from false positives.

• Monotonic versus time-of-day clock: when is each appropriate? The time-of-day clock gives wall-clock time, is NTP-synchronised and can jump; use it for timestamps shown to people. The monotonic clock only moves forward with a meaningless absolute value; use it for timeouts and elapsed time. Measuring a duration with the time-of-day clock gives nonsense when NTP steps the clock.

• Why is last-write-wins with timestamps unsafe, and how does Spanner make timestamps work? Clock skew lets a causally later write carry an earlier timestamp and be discarded, and equal timestamps need arbitrary tiebreaks. TrueTime returns an uncertainty interval; non-overlapping intervals are unambiguously ordered, and Spanner waits out the interval before committing, with GPS and atomic clocks keeping it to a few milliseconds.

• A leader checks its lease and then writes. What can go wrong? The process can pause between check and write (GC, VM migration, I/O stall), the lease expires, another leader is elected, and the old one resumes and writes: split brain. Fix with fencing tokens issued by the lock service and verified by the storage system, which rejects stale tokens.

• Why majority quorums rather than letting a node decide for itself? A node cannot tell whether it is alive but unreachable or truly failed. Any two majorities overlap in at least one node, so conflicting decisions cannot both pass, and a node outvoted must step down.

• When do you need Byzantine fault tolerance? When participants may be malicious or arbitrarily faulty and are not under one administrative domain (multi-party ledgers, blockchains) or hardware is exposed to radiation. Inside one organisation's datacenter, crash-recovery is the standard model and BFT buys little at high cost.

• Define safety and liveness with an example from a lock service. Safety: nothing bad happens, and a violation is a permanent fact; example, no two clients hold the lock at once. Liveness: something good eventually happens; example, a requester that does not crash eventually gets a response. Safety must hold under all faults; liveness may assume a majority is up and the network eventually recovers.

Pitfalls and misconceptions

• "No response means the request failed." It may have succeeded. Make operations idempotent so retries are safe.
• "Network partitions are rare." Switch misconfiguration, cable damage and cloud glitches produce them monthly; test with fault injection.
• "NTP keeps clocks in sync, so timestamps are comparable." Tens of milliseconds of error at best, occasional seconds, and clocks may step backwards.
• "Measure elapsed time with System.currentTimeMillis()." That is the time-of-day clock; use the monotonic clock.
• "The lease was valid a millisecond ago." A millisecond ago may be a minute ago after a GC pause. Only a token checked by the resource protects against a confused ex-leader.
• "A lock service gives mutual exclusion in a distributed system." Only with fencing; a lock relying on client-side timing is advisory.
• "Eventually consistent means consistent soon." It is a liveness property with no bound.
• "Partially synchronous means I can treat the system as synchronous." The point of the model is that bounds are sometimes exceeded; safety must not depend on them, only liveness may.

Key terms

Term	Meaning
Partial failure	Some components fail while others keep working
Asynchronous packet network	Messages may be lost, delayed or reordered with no upper bound
Network partition (netsplit)	Part of the network is cut off from the rest
Unbounded delay	No guaranteed maximum network or processing latency
Cascading failure	Load shifted from one failing node overwhelms others
Phi-accrual failure detector	An adaptive detector estimating failure probability from the latency distribution
Circuit switching	Reserved end-to-end bandwidth with bounded delay (telephone networks)
Time-of-day clock	Wall-clock time; NTP-synchronised; may jump
Monotonic clock	Always increases; only differences are meaningful
Clock drift	The rate a quartz clock runs fast or slow, around 200 ppm
Logical clock	A counter ordering events by causality rather than physical time
TrueTime	Spanner's clock API returning an uncertainty interval [earliest, latest]
Commit-wait	Spanner's deliberate delay for the interval length so timestamps are ordered
Stop-the-world GC	A garbage-collection phase that halts all application threads
Lease	A lock with an expiry that must be renewed
Quorum	A strict majority of nodes whose agreement defines the truth
Fencing token	A monotonically increasing number issued with a lease and verified by the resource
Byzantine fault	A node behaving arbitrarily or maliciously, including lying
Safety property	"Nothing bad happens"; a violation is permanent and must never occur
Liveness property	"Something good eventually happens"; may hold only under caveats

Further reading

• DDIA, Chapter 8, "The Trouble with Distributed Systems". Reference list: https://github.com/ept/ddia-references
• Bailis and Kingsbury, "The Network is Reliable", ACM Queue 2014: https://queue.acm.org/detail.cfm?id=2655736
• Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", CACM 1978: https://lamport.azurewebsites.net/pubs/time-clocks.pdf
• Corbett et al., "Spanner: Google's Globally-Distributed Database", OSDI 2012: https://www.usenix.org/conference/osdi12/technical-sessions/presentation/corbett
• Kleppmann, "How to do distributed locking": https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
• Hayashibara et al., "The Phi Accrual Failure Detector", SRDS 2004
• Lamport, Shostak and Pease, "The Byzantine Generals Problem", ACM TOPLAS 1982
• Fischer, Lynch and Paterson, "Impossibility of Distributed Consensus with One Faulty Process", JACM 1985
• Kyle Kingsbury's Jepsen analyses: https://jepsen.io/analyses