System Design Masterclass · Module 32 · Extension of Weeks 1 & 3
Time, Ordering & Failure Detection
The theory layer this course has been standing on without naming: why physical clocks can't order distributed events, the logical clocks that can (Lamport, vector, hybrid), the failure taxonomy from crash-stop to Byzantine, the Two Generals theorem behind Module 15's "exactly-once is an illusion," and how living systems actually decide who's dead — φ-accrual detectors and gossip.
~3h study~1h exercise1 interactive simFast track ~70 min
Fast track — can you already explain why LWW loses writes?
Compresses to ~70 min. The clock-skew motivation collapses; the logical-clock playground, the LWW verdict, and the failure-detection toolkit stay mandatory.
§01 takeaway · 5 min
§02 playground, all four experiments · 25 min · MANDATORY
§03 HLC & LWW, in full · 15 min · MANDATORY
§04 detection toolkit, in full · 20 min · MANDATORY
STEP 01
Physical clocks lie — and how much
SKIM
Fast-track takeawayEvery node's clock drifts (quartz: ~10–200 ppm — seconds per day); NTP corrects it to ~1 ms inside a datacenter, tens of ms across regions — and corrections can step time backwards, while leap-second smearing deliberately runs clocks wrong for hours. Consequence: two timestamps from different nodes closer together than the sync error bound cannot be ordered — node B can receive a message "before" node A sent it. Everything downstream follows: timestamp-ordered logs interleave wrongly, cross-node latency math needs one clock (M24's spans measure duration locally for this reason), token exp/nbf needs skew tolerance (M22), certificate validity checks fail on skewed hosts (M21), and lease expiry math must budget for drift (M19). The escape has two exits: buy hardware-bounded uncertainty (Spanner's TrueTime: GPS+atomic clocks exposing an interval, and waiting out the uncertainty before commit — expensive, rare), or stop using wall time for ordering entirely and use logical clocks — §02.
STEP 02
Logical clocks: ordering without time
MANDATORY
The foundation is the happens-before relation (→): a → b if they're on the same node in sequence, if a is a send and b its receive, or transitively. If neither a → b nor b → a, the events are concurrent (a ∥ b) — no observer can justify an order, and any "order" you impose is a policy choice. Two clock designs capture this with different fidelity:
Lamport timestamp — one counter per node: increment on each local event; stamp sends; on receive set L = max(local, received) + 1. Guarantees: a → b ⇒ L(a) < L(b). The converse fails: L(a) < L(b) tells you b didn't cause a — it cannot distinguish "a caused b" from "unrelated." Cheap total-ordering tiebreaker (L, then node-id) — Raft's term (M30) is a Lamport clock at cluster scope.
Vector clock — a counter per node, merged element-wise on receive. Now comparison is complete: VC(a) ≤ VC(b) element-wise ⇒ a → b; each greater in one slot ⇒ concurrent, detected — which is exactly what a store needs to say "conflict, both versions kept" (M04's Dynamo siblings) instead of silently picking one. Cost: O(nodes) metadata per event, and pruning is genuinely hard.
Logical clock playground · nodes A & B
Node A
Node B
Each event shows L (Lamport) and VC [A,B]. Create two local events on different nodes with no messages between them, then Compare — the vector clock will call them concurrent while Lamport numbers still suggest an order that isn't there. Then relate them with a message and compare again.
Try the four canonical experiments: (1) local@A then local@B, compare — concurrent, VC proves it; (2) A→B message, then local@B, compare the send and the later B event — ordered, both clocks agree; (3) build a chain A→B→A and see transitivity carried in the vectors; (4) note throughout that Lamport values always increase along arrows but comparing two arbitrary L values proves nothing about causality — the precise reason Lamport is enough for tiebreaking but not for conflict detection.
STEP 03
HLC, and the LWW verdict
MANDATORY
Hybrid Logical Clocks = (physical time, logical counter): tracks wall clock when it's moving forward sanely, falls back to logical increments when skew would violate happens-before. You get causality-safe ordering and human-readable, roughly-real timestamps — why CockroachDB and friends use HLC, and the right default if you're designing a distributed log/store and tempted to use System.currentTimeMillis().
The LWW verdict this module exists to deliver: last-writer-wins resolution (Cassandra cell timestamps, Redis CRDT LWW registers, most "simplest" merge policies) uses physical clocks to pick winners — so within the skew bound, concurrent writes are silently ordered by clock luck and the loser is deleted without trace. That's an acceptable policy for view counters and presence flags (M04's eventual-consistency tier), and an unacceptable one for entitlements, watchlists, or anything users notice — those need vector/version detection with a real merge (M04 §04), or single-writer-per-key routing (M05's ownership) that makes concurrency impossible by construction. Say it in reviews as: "LWW doesn't resolve conflicts, it hides them — is hiding acceptable for this data?"
Where you already met this: M16's version-guard CAS is a per-row logical clock; M19's fencing token is a per-lock one; M30's term is a per-cluster one; Kafka offsets (M15) are per-partition ones — monotonic counters standing in for time is the single most reused trick in this course, and now it has its name.
STEP 04
Failure: the taxonomy and the detectors
MANDATORY
The taxonomy, weakest to nastiest:crash-stop (dies, gone) · crash-recovery (dies, returns with disk state — what you actually design for, and why WALs exist, M27) · omission (messages silently dropped) · timing/gray (alive but slow or intermittently wrong — the hardest, M13's whole reason) · Byzantine (arbitrary/malicious behavior). Every protocol states its model: Raft tolerates crash-recovery, not Byzantine — a corrupted or hostile node can wreck an etcd cluster, which is why M21's zero-trust perimeter around the control plane isn't optional. Byzantine-tolerant consensus (PBFT-family) costs 3f+1 nodes and shows up in blockchains, not inside your trusted estate.
Two Generals, finally named: over a lossy channel, two parties can never reach certain agreement that both know the other knows — every ack needs an ack, forever. This is the theorem under M15/M16: delivery guarantees can only be at-least-once (retry into duplicates) or at-most-once (silence into loss); "exactly-once" is always at-least-once plus idempotent application. When someone proposes a protocol that "confirms receipt reliably," this is the two-word review comment.
You cannot distinguish slow from dead — so real detectors output suspicion, not verdicts. φ-accrual (Akka, Cassandra): model the history of heartbeat inter-arrival gaps, output φ = how improbable the current silence is; act at a threshold (φ≈8 ≈ 10⁻⁸ chance it's alive-and-slow). The design win is that the threshold adapts to observed jitter — a fixed 3-missed-heartbeats rule false-positives during every GC pause and load spike (M12's fixed-timeout lesson, applied to liveness). Tuning is the M08 trade again: aggressive φ = fast failover + flapping; conservative = slow detection + longer brownouts.
Gossip: membership without a master. Each node periodically exchanges its view (who's up, incarnation numbers, φ suspicions) with a few random peers; information spreads epidemically in O(log N) rounds. No coordinator, no single point of failure, tolerates partitions — the price is convergence delay and brief disagreement about who's alive (an AP choice, M03). Cassandra/Consul/Serf membership run on this; anti-entropy (M04's Merkle-tree repair) is the same epidemic idea applied to data instead of membership. Contrast with M30: consensus membership (etcd) is instant-and-consistent but quorum-bound; gossip is eventual-and-unkillable — pick per the stakes of being wrong.
Split-brain's full kit (collecting the course): quorum to prevent two actives (M30), fencing so a stale actor's writes bounce at the resource (M19), and — in stateful-hardware land — STONITH: forcibly power off the suspect node so "is it really dead?" becomes "yes, I made it so." Your cloud estate mostly gets STONITH free via instance termination; the concept matters when someone proposes a two-node HA pair with no third vote (M30 §04's witness objection, now with the traditional name).
Staff expectationThis module is mostly vocabulary that compresses arguments. "That's Two Generals — make the consumer idempotent" ends a meeting that would otherwise redesign acking for an hour. "LWW hides concurrent writes; is that acceptable for entitlements?" is a one-line design review. "Your detector is fixed-threshold; it'll flap under GC — use accrual or widen it" is a production save. Senior fluency isn't deriving these results; it's recognizing which one the room is currently rediscovering.
STEP 05
Exercise
MANDATORY
Fast trackStep 1 (~30 min): implementing vector-clock comparison makes concurrency detection permanent knowledge.
1
Implement both clocks. Java: a 3-node in-process simulation with Lamport and vector clocks side by side; generate random local events and messages, then write the comparator that classifies any two events as →, ←, or ∥. Verify: every Lamport-ordered concurrent pair your comparator finds is a would-be lost update under LWW.
2
See real skew. Compare clocks across your fleet (chronyc tracking/cloud NTP metrics) and find your actual bound; then grep one service's logs for cross-node "impossible" orderings (response logged before request). Write the one-paragraph policy: what your platform may and may not use wall-clock timestamps for.
3
Audit LWW exposure. List every store in your estate resolving conflicts by timestamp (Cassandra tables, Redis structures, any "updated_at wins" merge in application code). For each: what data, is silent loss acceptable, and if not — version-detection, single-writer routing, or CRDT (M04)? The entitlement-shaped ones go to the top.
4
Detector check. Find your platform's liveness decisions (LB health checks M08, k8s probes M29, any Cassandra/Akka φ config): fixed-threshold or adaptive? What happens during a 4-second GC pause — and did that already cause a flap incident you can now re-explain?
Self-check
Two services log the same request; B's "received" timestamp precedes A's "sent." List the possible explanations in likelihood order.
(1) Clock skew — if the gap is within your NTP bound (~1 ms DC, tens of ms cross-region), the timestamps are simply incomparable; (2) NTP step — one clock was corrected backwards between the two log lines; (3) actual causality violation — essentially never. The fix for debugging is a shared logical marker: propagate the trace ID with span parent-child links (M24), which encode happens-before explicitly and make wall-clock comparison unnecessary.
Why is Lamport enough for Raft's terms but not for Dynamo's conflict detection?
Raft needs a total order with the guarantee "higher term = later authority" — Lamport's a → b ⇒ L(a)<L(b) plus a tiebreak gives exactly that, cheaply. Dynamo needs the *converse* direction: given two replicas' versions, decide whether one descends from the other or they're concurrent — Lamport can't distinguish those, so it would silently order concurrent writes (becoming LWW). Vector clocks make the comparison complete, at O(nodes) metadata cost. Rule: total order for authority → Lamport-class; concurrency detection for data → vector-class.
A colleague proposes fixing duplicate processing by having the broker "confirm the consumer really got it" with a second ack round. Respond in three sentences.
That's the Two Generals problem: the confirmation itself can be lost, so certainty never terminates — a second ack round just moves the ambiguity, it can't remove it. The broker must choose redelivery-on-doubt (at-least-once) or silence-on-doubt (at-most-once); for our data we choose at-least-once. Duplicates are therefore a consumer-side contract: idempotent application via M16's patterns, which we already have machinery for.
Cassandra marks a node down during every major GC pause, triggering repair storms. Which knob and which module's trade-off?
The φ-accrual threshold (phi_convict_threshold): it's converting "improbably long silence" into "down," and the pause pushes past it. Raising it (e.g. 8 → 12) trades slower true-failure detection for immunity to pause-length silences — M08's fast-detection vs flapping trade, chosen adaptively. The deeper fix is shrinking the pauses (M29's CPU-limit/GC tuning) — but the detector must still be sized for the pauses you actually have, not the ones you wish you had.