Part 7 · Failure

The Trouble with Distributed Systems: Partial Failure, Clocks, and Fencing

Lesson 14 drew the transaction boundary: it showed how messaging, idempotency keys, and the outbox keep a multi-step operation atomic across a queue — but every guarantee there leaned on the assumption that a node either runs or has cleanly stopped. Now we confront what happens when that assumption breaks. Transactions (lesson 13) work on a single machine because one process controls one disk and either commits or aborts cleanly. But replication (08–09), partitioning (11), and any multi-node operation stretch that machine across a network — and the network changes the rules. A single computer is honest: it works or it crashes, and you can tell which. A distributed system is not: some parts work while others fail, pause, or vanish, and from any one node you frequently cannot tell which. This lesson confronts the new hazards that creates — partial failure, unreliable failure detection, unreliable clocks, and processes that freeze mid-operation — and the one mechanism, the fencing token, that makes shared state safe anyway. This is the home of "unreliable clocks" and "fencing tokens"; lessons 16 and 17 build consistency and consensus on top of it.

DDIA source

Arc drawn from Martin Kleppmann, Designing Data-Intensive Applications, Chapter 8 (The Trouble with Distributed Systems) — partial failure and unreliable networks, unreliable clocks (time-of-day vs monotonic, NTP, clock skew), process pauses, fencing tokens, and Byzantine faults. Original synthesis; ML-infra framings are ours.

Linear position

Prerequisite: Lessons 08–09 (replication, the replication log, last-write-wins) and 13 (transactions, atomic commit). We rely on "a write must cross the network to reach replicas" and on LWW's dependence on comparable timestamps, and we will explain why that dependence is dangerous.
New capability: Reason precisely about what a timeout does and does not tell you; refuse to order events by wall-clock timestamp; and protect a lock-protected resource against a paused, zombie owner using monotonically increasing fencing tokens.

The plan

Six moves. (1) Partial failure — why a distributed system fails differently from one machine, and why the network gives you no reliable failure detector. (2) Timeouts are a guess — converting "no reply" into a decision, trading false positives against slow detection. (3) Unreliable clocks — time-of-day vs monotonic clocks, clock skew, NTP vs PTP vs TrueTime accuracy, a worked number showing two writes ordered wrong by timestamp, and the cheap fix real databases ship: the hybrid logical clock. (4) Process pauses and the zombie-owner hazard — a GC pause holds a lease past expiry and corrupts shared state. (5) Fencing tokens — the fix, walked through an ASCII timeline. (6) System models — the timing and fault models an algorithm assumes, and the 3f + 1 boundary for Byzantine tolerance.

1 · Partial failure: the defining hazard

On a single machine, faults are deterministic and total. If you write past the end of an array the program crashes; if the RAM is bad the machine halts. Either the whole computer is doing its job or it has stopped, and software is written to assume exactly that: "if anything is wrong, fail fast and let the operator restart." There is no in-between state where half the CPU is computing correct answers and half is silently returning garbage.

A distributed system — two or more machines coordinating over a network — has no such luxury. Its defining feature is partial failure: some components are broken or unreachable while the rest keep running and keep making decisions. And these partial failures are nondeterministic. A request crossing the network may be delayed by a congested switch, dropped entirely, delivered but its reply lost, or delivered and processed while the sender gives up waiting. The same operation can succeed, fail, or hang on different attempts for reasons no node can observe directly.

The deepest consequence is that you cannot reliably tell a crashed node from a slow one. When node A sends a request to node B and hears nothing back, every one of these is consistent with the silence:

A --- request ---> B what actually happened, from A's view, is UNKNOWN: (1) request lost in the network -> B never saw it (2) B is slow / overloaded -> B is processing it right now (3) B crashed before processing -> request never ran (4) B processed it, reply lost -> request ran; A just didn't hear (5) B is GC-paused for 8 s -> B is frozen but alive; reply is coming A observes the SAME THING in all five cases: no response yet.

There is no built-in oracle on the network that tells you "B is dead." A failure detector — the component that decides whether a remote node is up — can only ever guess, because the only evidence available is the presence or absence of replies within some deadline. That guess is the subject of the next section, and the impossibility of making it perfect is what makes everything downstream (consensus, leader election, locks) genuinely hard rather than merely fiddly.

Why "just make the network reliable" doesn't work

You can buy a better network — lower loss, tighter latency — but you cannot buy a bounded one cheaply enough to matter. Datacenter links still drop packets, switches still buffer under load, and a fully GC-paused or VM-migrating node looks identical to a partitioned one from outside. Systems that assume a synchronous network (every message arrives within a known bound) work in testing and corrupt data in production. The robust assumption is the partially synchronous one: usually fast, occasionally arbitrarily slow, with no advance warning of which.

2 · Timeouts: turning uncertainty into a decision

Since the network won't tell you whether B is dead, you pick a deadline and act on it. A timeout is that deadline: "if B has not replied within τ, treat B as failed." A timeout does not discover a failure; it declares one. It converts the irreducible uncertainty of §1 into a yes/no decision you can build on — and like any forced decision under uncertainty, it can be wrong in two opposite ways.

Timeout choice	Buys	Costs
Short τ	Fast detection; quick failover; resources freed promptly	False positives: a merely-slow node is declared dead, a healthy leader is replaced mid-flight, work is duplicated by premature retries — a retry storm that piles load on a system that was only briefly slow
Long τ	Few false suspicions; tolerates tail-latency spikes and short pauses	Slow detection: a genuinely dead node keeps receiving traffic for seconds; failover and recovery lag; held resources (locks, connections) linger

There is no τ that is right for both a fast-and-healthy and a slow-but-alive node, because from the outside those two states are identical (§1). So a timeout is permanently a bet on which world you are in. Two engineering consequences follow and you will see them everywhere:

→Every remote operation is "maybe-executed." A timed-out request may have run, may not have, may have run twice (if you retried). That single fact is the root of idempotency keys, deduplicated request IDs, and exactly-once stream processing (lesson 19). Retrying is only safe if the operation is idempotent — applying it twice equals applying it once.

→Adaptive timeouts beat fixed ones. Rather than a hard-coded τ, mature systems measure the observed round-trip distribution and set τ as, say, a high percentile plus margin — so τ tracks real conditions instead of a guess made at design time.

Worked number — the retry-storm trap

Suppose B's normal reply time is 10 ms, but once a minute a GC pause makes it take 400 ms. You set τ = 50 ms and retry on timeout. During the pause, every in-flight client times out and retries; if 2,000 requests/second are hitting B, a 400 ms pause produces roughly 2,000 × 0.4 = 800 timed-out requests, each retried — so B, already frozen, wakes to 1,600 requests (originals it never answered plus retries) instead of 800. The retries amplify load exactly when B is weakest, and if they aren't idempotent, each duplicate also double-applies its side effect. Raising τ to, say, 500 ms removes the false positive entirely at the cost of detecting a real death 450 ms slower. That is the whole trade in one example.

3 · Unreliable clocks: two kinds, and why you can't order events with them

Coordinating nodes are tempted to use time to make decisions — "the newer write wins," "the lease expires at 12:00:05." But the clocks on different machines disagree, and there are actually two different kinds of clock that answer different questions. Conflating them is a classic source of corruption.

Time-of-day clock

Returns wall-clock calendar time (e.g. "2026-06-17 12:00:05.123 UTC"). Synchronized to the outside world by NTP (the Network Time Protocol, which slews the clock toward a time server). Can jump forward or backward when NTP corrects it, and can skip or repeat seconds. Good for: timestamps a human reads, logging. Bad for measuring elapsed time — a backward jump can make a duration negative.

Monotonic clock

Returns a count that only ever moves forward (e.g. nanoseconds since boot). Has no relation to calendar time and is not comparable across machines, but on one machine it never jumps back. Good for: measuring how long something took, computing timeouts and lease durations. This is what your timeout code in §2 should read.

Clock skew is the difference between two machines' time-of-day clocks at the same real instant. Even with NTP running, skew is routinely tens of milliseconds in a datacenter and can be much worse: an NTP sync only happens periodically, the round-trip to the time server is itself uncertain, a machine's quartz oscillator drifts between syncs, and a leap second or a misconfigured server can push skew into seconds. NTP narrows skew; it does not eliminate it, and it gives you no guaranteed upper bound you can rely on for correctness.

Worked number — last-write-wins ordered the writes WRONG

Recall last-write-wins (LWW) from lesson 09: on a conflict, keep the value with the larger timestamp. Suppose node X's clock is 100 ms ahead of node Y's (a clock skew of 100 ms — well within real-world ranges). Take a base wall time of 1000 ms and watch the two writes:

real time event timestamp stamped on the write --------- ------------------------- -------------------------------- T = 40 ms X writes name = "Sam" X's clock = 1000 + 40 + 100 skew = 1140 T = 120 ms Y writes name = "Samantha" Y's clock = 1000 + 120 = 1120 REAL order: "Sam" (40 ms) THEN "Samantha" (120 ms) -> "Samantha" is newer LWW compares 1140 ("Sam") vs 1120 ("Samantha") -> keeps "Sam" *** WRONG ***

"Samantha" was written 80 ms later in real time and should have won, but X's 100 ms skew stamped the earlier "Sam" with the larger timestamp. LWW keeps "Sam" and silently discards the genuinely newer write with no error. Any two writes that land within the skew window (here, 100 ms) of each other can be ordered backwards.

The rule that follows: never order events for correctness by comparing wall-clock timestamps across nodes. Wall time is fine for things that tolerate being approximate — display, logging, expiry with a generous safety margin. When the correctness of a decision depends on order ("which write is newer," "who is the leader," "did A happen before B"), you need either a logical ordering that doesn't pretend to know real time — causal order via version vectors (lesson 09) or Lamport/vector clocks, formalized in lesson 16 — or explicit coordination through consensus (lesson 17). Time-of-day timestamps are a measurement, not an order.

How close can clocks be brought, and at what cost? Three points on the accuracy ladder are worth knowing by name, because the gap between them is the whole engineering story:

NTP — tens of ms over WAN

NTP (the Network Time Protocol) walks a hierarchy of time servers and slews each client toward them. It infers the offset from the round-trip to the server and assumes the path is symmetric (request and reply take equal time). When routes are asymmetric — common on the public internet — that assumption is wrong and the inferred offset is off by half the asymmetry. Realistic accuracy: a few ms inside a datacenter, tens of ms over a WAN, and worse during congestion. A mishandled leap second (a one-second calendar correction) can make a clock repeat or skip a second, which has crashed real systems.

PTP — sub-microsecond in a DC

PTP (the Precision Time Protocol, IEEE 1588) reaches sub-microsecond accuracy, a thousand-fold better than NTP, by timestamping packets in the network-card hardware (so OS scheduling jitter never enters the measurement) and using switches that correct for their own buffering delay. The price is that it needs PTP-aware NICs and switches — so it lives inside one datacenter, not across the WAN.

TrueTime — bounded uncertainty

Google's TrueTime (under Spanner) refuses to pretend the clock is a point. It returns an interval [earliest, latest] guaranteed to contain the true time, keeping the interval small (single-digit ms) with GPS receivers and atomic clocks in every datacenter. Knowing the bound is what makes ordering safe — see below.

TrueTime / Spanner — pay the uncertainty, then order safely

The trick is not a more accurate clock but an honest one: TrueTime hands back [earliest, latest] with a hard guarantee that real time lies inside, and Spanner uses it with commit-wait. To commit a transaction at timestamp latest, Spanner deliberately waits out the uncertainty — it sleeps until TrueTime's earliest has moved past latest, i.e. until even the slowest-running clock agrees the chosen timestamp is now in the past — before releasing the result.

commit T1 at timestamp ts1. uncertainty interval width = ε (say 6 ms) pick ts1 = TrueTime.now().latest WAIT until TrueTime.now().earliest > ts1 (sleeps ~ε) only then release locks / make T1 visible guarantee: any T2 that STARTS after T1 finished gets ts2 > ts1, because by the time T1 was visible, every clock had already passed ts1. => timestamp order == real-time order (linearizable, "external consistency")

So the cost is a commit latency of about ε on every transaction (smaller ε = less wait, which is why Google spends on GPS + atomic clocks to shrink it), in exchange for timestamps that can be ordered as if they were real time. It is the exception that proves the rule: making wall-clock time trustworthy for ordering is expensive enough that most systems don't, and reach for logical ordering (lesson 16) instead.

TrueTime is the expensive answer: buy better hardware to shrink the uncertainty, then pay latency to wait it out. There is a cheap answer that most distributed databases actually ship, and it is worth meeting here because it lives exactly at the seam between this lesson's physical clocks and the logical clocks of lesson 16: the hybrid logical clock.

Hybrid logical clocks (HLC) — causality for the price of a counter

Two pure options each fail in one direction. A physical clock tracks real time but can jump backward on an NTP correction — and a backward jump can stamp an effect before its cause, the §3 sin. A logical (Lamport) clock (lesson 16) never goes backward and always respects causality, but it is just a counter: one chatty node can inflate it far beyond real time, so the number tells you order but no longer means anything as a time (you can't ask "roughly when did this happen?" or expire on it).

An HLC timestamp is the pair (l, c) — a physical part l (a wall-clock reading) and a small logical counter c — and the update rule takes the best of both:

on a local event, or before sending: l_new = max(l_prev, physical_clock_now()) if l_new == l_prev: c = c + 1 // physical time didn't advance -> bump counter else: c = 0 // physical time moved -> reset counter on receiving a message stamped (l_msg, c_msg): l_new = max(l_prev, l_msg, physical_clock_now()) if l_new == l_prev == l_msg: c = max(c_prev, c_msg) + 1 // both stored times tie elif l_new == l_prev: c = c_prev + 1 // our stored time wins elif l_new == l_msg: c = c_msg + 1 // the message's time wins else: c = 0 // physical time advanced past both // -> the received timestamp can only push our clock FORWARD, never back; // the counter c only ever breaks ties WITHIN one physical-time value

Because every step takes a max and the counter only ever breaks ties within one physical millisecond, an HLC never moves backward — so if event a happens-before event b, then HLC(a) < HLC(b), the same causality guarantee a Lamport clock gives. But unlike a Lamport counter, the physical part l stays pinned within the clock-skew bound of real wall time (it is a max of physical readings, so it can run at most one skew-window ahead and never behind a correct clock). You get a timestamp that is both a legal causal order and a meaningful approximate wall-clock time, in about 64 bits, with no special hardware and no commit-wait.

The bill, and the reason it isn't a free TrueTime: an HLC gives you causal order, not external (real-time) order. For two concurrent writes — neither caused the other — it will pick some order, but not necessarily the order a wall clock would have seen, and it cannot certify "T1 really finished before T2 started in real time" the way commit-wait does. That is exactly the right trade for systems that want causal consistency cheaply: CockroachDB, YugabyteDB, and MongoDB's cluster time all stamp events with HLCs. TrueTime pays hardware + latency to buy real-time order; HLC pays a 2-byte counter to buy causal order. Lesson 16 makes the "causal vs linearizable" distinction underneath this trade precise.

4 · Process pauses and the zombie owner

So far the danger has been the network and the clock. The third hazard is closer to home: your own process can freeze, for far longer than you expect, with no warning and no way to know afterward how long it was out. Causes are everywhere — a stop-the-world garbage-collection pause, the hypervisor suspending a VM to live-migrate it to another host, the OS swapping the process out under memory pressure, a laptop closing its lid mid-request. Any of these can stop a running process for hundreds of milliseconds to several seconds.

This turns a comfortable mechanism dangerous: the lease. A lease is a lock with an expiry — a node acquires the right to be "the leader" or "the owner of partition 7" for, say, 10 seconds, and must renew before then or lose it. Leases are how systems avoid two nodes both thinking they're the leader. The fatal interaction:

client 1 holds the lease, valid until T = 10 s. It checks: "lease valid? yes." Then — before it acts — it suffers a 6 s GC pause. T=4s client 1: "lease ok until 10s" ... begins to write to storage T=4s *** GC PAUSE — client 1 frozen, sees nothing *** T=10s lease expires (client 1 still frozen, does not know) T=11s lock service grants the lease to client 2 (client 1 looks dead) T=12s client 2, now the rightful owner, writes to storage T=13s *** client 1 WAKES UP *** — still believes "lease ok until 10s" T=13s client 1 completes its write to storage Now BOTH wrote. Client 1 is a ZOMBIE: it lost ownership while frozen and has no way to know its check at T=4s is stale.

Client 1 did everything right. It checked the lease, the check passed, and only then did it act. The pause inserted itself between the check and the action, and when it resumed it had no signal that the world had moved on. A lease expiry can't help, because expiry is judged by the wall clock (§3) and the frozen process can't even read it. This is the core distributed hazard: a node that believes it still holds a lock or lease after a pause, and corrupts shared state by acting on that stale belief. The lock service granting the lease to client 2 was not enough — the storage accepted client 1's late write because it had no idea client 1 was deposed.

5 · Fencing tokens: making the zombie's write harmless

The fix is to stop trusting the lock holder's belief and instead make the protected resource itself reject stale writers. A fencing token is a number the lock service hands out with every lease grant, and it increases monotonically: each new grant gets a strictly higher token than the last. The client must attach its token to every write. The storage system remembers the highest token it has ever accepted and refuses any write carrying a lower token. A deposed zombie necessarily holds an old (lower) token, so its late write is fenced off.

lock service hands out monotonically increasing tokens: 33, then 34, then 35... storage remembers the highest token it has accepted and rejects anything lower. T=4s lock svc -> client 1: lease + token = 33 T=4s client 1 begins write(token=33) ... then GC-pauses, frozen T=10s client 1's lease expires (client 1 still frozen) T=11s lock svc -> client 2: lease + token = 34 (strictly higher) T=12s client 2 -> storage: write(token=34) storage: 34 >= highest-seen(0) -> ACCEPT, record highest = 34 T=13s client 1 WAKES, still thinks it owns the lease T=13s client 1 -> storage: write(token=33) storage: 33 < highest-seen(34) -> *** REJECT *** (fenced off) The zombie's stale write is refused by the resource itself. Client 1 never had to know it was deposed — the token made it safe.

Three properties make this work, and each matters:

Monotonic and issued by one authority. Tokens come from the lock/lease service and strictly increase, so a later owner always carries a higher token than an earlier one. (Producing a monotonically increasing token across failures is itself a consensus problem — exactly what coordination services like ZooKeeper/etcd provide; lesson 17.)
Enforced at the resource, not the client. The storage system — the thing being protected — does the check. You cannot rely on the client to fence itself, because the dangerous client is the one whose view of the world is wrong. This is the same lesson as the routing guardrail in other tracks: the resource enforces the rule, not the actor.
Cheap. The check is a single integer comparison per write. The cost is plumbing: the token must thread from the lock service through the client to the storage layer, and the storage layer must persist "highest token seen."

This pattern is everywhere shared mutable state meets distributed locks: a model registry that must accept a promotion only from the current deployment worker (a stale worker resuming after a pause must be fenced); a single-writer shard leader (lesson 09) writing to a log; a workflow executor that must not let a replaced instance double-apply a step. In all of them the rule is identical — hand out a monotonic token with the lease, and have the resource reject stale tokens.

6 · System models: the assumptions an algorithm is allowed to make

Everything above — timeouts, clocks, pauses — is really about what you are allowed to assume. A distributed algorithm is only "correct" relative to a system model: an explicit statement of how time behaves and how nodes are allowed to fail. State the model wrong and a proof is worthless. There are two axes.

The timing model says how much you may assume about delays:

timing model what you may assume realism ----------------- ---------------------------------- ------------------------ synchronous every message arrives within a UNREALISTIC — no real KNOWN bound; clock drift bounded network guarantees this partially usually behaves synchronously, but REALISTIC — the right synchronous occasionally exceeds any bound, default (matches the §1 with no warning of which warn callout) asynchronous NO timing bound at all; a message too weak to do much — may take arbitrarily long this is the FLP world (L17)

The fault model says how nodes are allowed to misbehave, from gentlest to harshest:

Crash-stop. A node works correctly until it halts, and once halted it never comes back. Simplest to reason about.
Crash-recovery. A node may crash and later restart, losing in-memory state but keeping anything it wrote to stable storage. This is what real machines do — and the reason participants in a protocol must write durable promises (you will see this in 2PC and consensus, lesson 17).
Byzantine. A node may do anything — the harshest model, below.

Almost everything in this track assumes a partially synchronous, crash-recovery model with non-Byzantine nodes. That is the honest description of a normal datacenter, and it is exactly strong enough to make majority consensus (lesson 17) work while being weak enough to survive production.

Byzantine faults, and the 3f + 1 boundary

Everything above assumed nodes are honest but unreliable: they may be slow, crash, or pause, but they don't lie. A Byzantine fault is a node that behaves arbitrarily or maliciously — sending different answers to different peers, forging messages, claiming a token it was never issued. The fault model changes the arithmetic:

crash faults (honest, may die): tolerate f failures with 2f + 1 nodes (any two majorities overlap in 1 honest node — L17) Byzantine faults (may lie): tolerate f liars with 3f + 1 nodes

The extra f is the price of dishonesty. With crash faults a single honest node shared between two quorums settles disagreements; with liars you must out-vote them and tolerate that up to f of the votes you collect are forged, so any decision needs 2f + 1 matching honest votes out of 3f + 1 total. Byzantine fault tolerance (BFT) also needs cryptographic message signing, and is the domain of aerospace, adversarial multi-party settings, and blockchains. Inside a single trusted datacenter, where you control all the nodes, the standard and reasonable assumption is the non-Byzantine one — so the rest of this track (consensus in lesson 17 included) assumes nodes may crash or pause but do not lie, and uses the cheaper 2f + 1.

Failure modes

Timeout = truth. Treating "no reply" as "node is dead and request didn't run." Leads to duplicated side effects on retry and to replacing leaders that were only slow. Symptom: double-charges, double-deploys, flapping leadership.
Retry storm. A short timeout plus aggressive non-idempotent retries multiplies load on an already-struggling node (see §2 worked number). Symptom: a brief slowdown cascades into an outage.
Wall-clock ordering. Using time-of-day timestamps to decide which write is newer (LWW) or who is leader. Clock skew silently reverses order and drops the genuinely newer write. Symptom: edits "disappear" with no error, correlated with no obvious cause.
Monotonic/wall-clock mix-up. Measuring a duration or a lease with a time-of-day clock that can jump backward, producing negative or absurd elapsed times. Symptom: a lease "expires in the past," a latency metric goes negative.
Zombie owner. A paused process resumes and writes under a lease it no longer holds; the storage accepts it because nothing checks. Symptom: corruption from a node everyone thought was gone.
Lock without fencing. A distributed lock that the protected resource does not enforce — the lock is advisory only. Symptom: the lock "works" in tests but lets a paused holder corrupt state in production.

Decision checklist

For each remote call: is it idempotent? If not, is there a dedup/idempotency key so a retry after timeout is safe?
Is the timeout adaptive (tracking observed latency) rather than a guessed constant? Does retry back off to avoid a storm?
Are you measuring durations and lease times with a monotonic clock, and showing wall time only for display/logging?
Does any correctness decision depend on comparing timestamps across nodes? If so, replace it with causal/logical ordering (16) or consensus (17).
If LWW is in use, is silently losing concurrent writes genuinely acceptable for this data (cache, last-seen) — and do you know clocks decide the winner?
Does every lock/lease hand out a monotonically increasing fencing token, and does the protected resource reject lower tokens?
Is the token authority a real consensus-backed coordination service (17), not a single node?
Are Byzantine faults actually out of scope (single trusted datacenter)? If not, you need BFT, not this.

Checkpoint exercise

Try it

You run a model registry. A "deployment worker" acquires a 10 s lease and then promotes a candidate model to production by writing to the registry. (a) Sketch the failure where a worker is granted the lease, GC-pauses for 8 s, a second worker is granted the lease and promotes model B, and the first worker wakes and promotes model A — show why both writes land and the registry ends up wrong. (b) Add fencing tokens: state exactly what the lease service issues, what the worker sends with its promote call, and what check the registry performs, then re-run your timeline and show the first worker's write being rejected. (c) Your monitoring computes "time since last promotion" by subtracting two timestamps. Which clock must each timestamp come from, and what bug appears if you use the wrong one across a NTP correction?

Where this points next

This lesson catalogued the hazards — partial failure, untrustworthy detection, skewed clocks, frozen processes — and gave one concrete defense (fencing) for one concrete problem (a zombie corrupting shared state). But it left the big question open: if we cannot order events by the clock, what is the strongest ordering and consistency guarantee a distributed system can actually offer, and at what cost? Lesson 16 answers that. It defines causality precisely (the happens-before relation and the version/vector clocks that track it without wall time), then climbs to linearizability — the guarantee that the system behaves as if there were a single up-to-date copy of the data, so every operation appears to take effect at one instant between its call and its return. We will see why linearizability is exactly what a correct lock or leader election needs, why it forces a real latency cost, and how it trades against availability when the network partitions — turning the informal "you need coordination for correctness" of this lesson into a formal hierarchy.

Where is truth?

For a fenced, lease-protected resource, "truth" about who may write right now is split deliberately. System of record: the lock/lease service holds the authoritative grant and the monotonic fencing-token counter (the latest token is the truth of current ownership); the protected resource (storage) holds the authoritative "highest token seen." Copies / derived views: each client's cached belief "I still hold the lease until T" — a derived, possibly-stale view that a pause can falsify. Freshness budget: the lease duration plus skew margin; a belief older than that must not be acted on, and durations are measured on a monotonic clock, never wall time. Owner: the lock/lease service issues and increments tokens; the resource enforces them. Deletion path: on lease expiry the grant lapses and the next grant supersedes it — no explicit revoke is needed, because a higher token silently invalidates all lower ones. Reconciliation / repair: a deposed zombie's write is rejected at the resource by the token check, and the client recovers by re-acquiring a fresh (higher) token. Evidence it is correct: the resource refuses any write carrying a token below its highest-seen, so two writers can never both commit under the same resource — the single-integer comparison is the proof.

Takeaway

A distributed system fails partially and nondeterministically: parts break while others run, and from any one node you cannot reliably distinguish a crashed peer from a slow one — the network offers no perfect failure detector. A timeout is therefore a guess, trading false positives (and retry storms) against slow detection, which is why every remote call must be treated as maybe-executed and idempotent retries matter. Clocks are two different things — a time-of-day clock that NTP can jump backward, and a monotonic clock that only moves forward — and because time-of-day clocks across nodes are skewed by tens of milliseconds or more, you must never order events for correctness by comparing wall-clock timestamps (last-write-wins can silently keep the older write when two land within the skew window). Worse, your own process can freeze for seconds on a GC pause or VM migration and become a zombie that acts on a lease it no longer holds. The robust fix is the fencing token: the lock service issues a monotonically increasing number with each lease, and the protected resource rejects any write carrying a token lower than the highest it has seen — so the deposed zombie's stale write is refused by the resource itself, no matter what the zombie believes. (Byzantine faults, where nodes lie, are out of scope for a trusted datacenter.) The deeper moral: for correctness, replace clocks and beliefs with explicit, enforceable order — built in lessons 16 and 17.

Interview prompts

Why is a distributed system fundamentally harder than a single machine? (§1 — partial, nondeterministic failure: some parts fail while others keep deciding, and you cannot reliably tell a crashed node from a slow one because the network gives no perfect failure detector.)
What does a request timeout actually tell you, and what are the failure modes of setting it short vs long? (§2 — it declares a failure rather than discovering one; short τ gives fast detection but false positives and retry storms, long τ avoids false suspicion but detects real death slowly. Treat every timed-out call as maybe-executed.)
Distinguish a time-of-day clock from a monotonic clock and say which to use for a lease duration. (§3 — time-of-day tracks calendar time via NTP and can jump backward; monotonic only moves forward. Use monotonic to measure durations and timeouts; time-of-day only for display/logging.)
Why is last-write-wins by wall-clock timestamp unsafe? Give the numeric intuition. (§3 — clock skew of, e.g., 100 ms can reverse the real order of two writes that land within that window, so LWW keeps the older one and silently discards the genuinely newer write. Order by causal/logical clocks (16) or consensus (17) instead.)
Walk through how a GC pause can corrupt shared state under a lease. (§4 — the holder checks the lease (valid), then pauses past expiry; the lease is reassigned; the holder wakes still believing it owns the lease and writes — a zombie acting on a stale belief, with no signal that it was deposed.)
What is a fencing token and exactly where is it enforced? (§5 — a monotonically increasing number issued by the lock service per lease; the client attaches it to every write; the protected resource remembers the highest token seen and rejects any lower one, so a zombie's stale write is refused. Enforcement is at the resource, not the client.)
How accurate is NTP, and how do PTP and TrueTime improve on it? (§3 — NTP gives a few ms in a datacenter, tens of ms over a WAN, degraded by asymmetric routes and leap seconds. PTP reaches sub-microsecond with hardware timestamping but only within a datacenter. TrueTime returns a bounded interval [earliest, latest] using GPS + atomic clocks, and Spanner waits out that uncertainty (commit-wait) so timestamp order equals real-time order.)
What is a hybrid logical clock, and what does it buy over a plain wall clock or a Lamport clock? (§3 — an (l, c) pair whose physical part l is a max of wall-clock readings and whose counter c breaks ties within one millisecond. It never moves backward, so it preserves causality (a happens-before b ⇒ HLC(a) < HLC(b)) like a Lamport clock, while l stays within clock-skew of real time so the timestamp is still a meaningful approximate wall time — all in ~64 bits, no special hardware, no commit-wait. The catch: it gives causal order, not the real-time/external order TrueTime's commit-wait buys. Used by CockroachDB, YugabyteDB, MongoDB cluster time.)
Name the three timing models and the three fault models, and the one pair this track assumes. (§6 — timing: synchronous / partially synchronous / asynchronous; faults: crash-stop / crash-recovery / Byzantine. A normal datacenter is partially synchronous + crash-recovery + non-Byzantine, which is exactly strong enough for majority consensus.)
When do you need Byzantine fault tolerance, and how does the node count change? (§6 — when nodes may lie or behave maliciously (adversarial/multi-party, blockchains); BFT needs 3f + 1 nodes plus message signing vs 2f + 1 for honest crash faults. In a single trusted datacenter you assume non-Byzantine nodes, which is far cheaper.)