Unit 5.1 · about 5 h
266 / 324Partial failure, clocks and event ordering
Assume Programming's cancellation-timeouts-retries unit. Here the question is what the caller can know after a timeout, and which event orders remain defensible when clocks disagree.
- explain
- derive
You can now
- Explain why a timeout cannot distinguish a lost request, a paused node and a lost reply.
- Assign physical and logical timestamps to a message history and identify causal and concurrent events.
- Choose a local clock for elapsed time without treating it as a cross-machine ordering oracle.
Covers
- Partial failure and unreliable timing assumptions
- Physical clocks, logical clocks and event ordering
Study, in this order
2 steps
- DDIA, 2nd edition: uncertain outcomes and physical clocksDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 9, Faults and Partial Failures and Unreliable Networks through Timeouts and Unbounded Delays, pp. 346 to 354; Unreliable Clocks through Timestamps for ordering events, pp. 358 to 364
- DDIA, 2nd edition: causal order and logical clocksDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 6, The happens-before relation and concurrency, pp. 238 to 239, and Version vectors, p. 242; Chapter 10, Logical Clocks, pp. 420 to 422
Focus on
- A timeout is an observation of silence, not proof of non-execution. Preserve an unknown outcome in the history.
- Use monotonic time for local durations. Wall-clock readings can disagree across nodes; local monotonic readings have no shared epoch.
- Happens-before follows process order, send-to-receive edges and transitivity. A smaller Lamport timestamp does not prove a causal dependency.
- Distinguish scalar clocks that order events from vectors that can expose concurrency. Neither provides consensus or elapsed seconds.
Reproduce closed-book
write(x,1) and times out; in one the request is dropped, in the other S applies it and the reply is dropped. Check the clocks and indistinguishability by hand; the numbers are logical counters, not measured time.Traps
- Comparing monotonic clock values from two hosts as if they were UTC timestamps.
- Treating timestamp order as a proof of causality or as evidence that an acknowledged write is durable.
- Interpreting a timeout as permission to repeat an externally visible effect without checking its identity.
Practice
Gossip Glomers Challenge 1: Echo
Specification; Installing Maelstrom; Running our node in Maelstrom with the one-node echo workload
First build the JSON-line node harness and correlate replies with in_reply_to; Unique ID Generation and Broadcast reuse it. It is protocol setup, not a new socket-framing exercise. Maelstrom needs OpenJDK, Graphviz and gnuplot, and the challenges were tested against Maelstrom 0.2.3; a JDK container such as eclipse-temurin:21 avoids a host Java install. Nodes can be written in Python; the tutorial's Go code needs a Go toolchain.
Gossip Glomers Challenge 2: Unique ID Generation
Specification, RPC generate, and Evaluation with the unique-ids workload
After Echo, implement IDs without assuming synchronized clocks, with the same Maelstrom setup. Explain why \((\text{node ID}, \text{counter})\) needs persistent counters or fresh incarnation IDs if restarts are added; the challenge does not crash nodes. Its workload tests uniqueness and total availability under partitions, not monotonicity or fencing.
Self-test
-
Can the caller tell a dropped request from a dropped reply after a timeout?
Not from silence alone. The operation may have executed, so its outcome is unknown. -
If \(L(a) < L(b)\), must \(a\) happen before \(b\)?
No. Causal order implies increasing Lamport counters, but unrelated events can also have different counters. -
What do vectors \((2,1)\) and \((1,2)\) tell you?
Neither dominates the other componentwise. Under the vector algorithm's causal tracking assumptions, the represented events are concurrent. -
Does a monotonic clock make an expired lease safe?
No. A process can pause or a request can be delayed after a lease check. The receiving resource must enforce ownership.
Completion criterion
Stop when
You recover the five counters without the source, distinguish the two timeout executions, and defend your ID scheme's uniqueness and restart assumptions.
Mark passed, then open 5.2 Only mark this when you can do it without notes.Leads to
- 5.2 Replication, quorums and consensus vocabulary Apply uncertain failure detection to replication and failover.
Comes after
- 6.7 Failure domains, correctness signals and safe rolloutReason about ordering under the same partitions.
Resources for this unit
- Designing Data-Intensive Applications, 2nd edition - distributed data path Read the selected chapters on replication, partitioning, distributed-system trouble, consistency and consensus, batch processing and stream processing. For each guarantee, write its assumptions, a confirming history and one counterexample outside the boundary.
Also in this section
- Gossip Glomers - Echo, Unique ID and Broadcast Complete Challenge 1 Echo, Challenge 2 Unique ID Generation and Challenge 3a Single-Node Broadcast. Add 3b Multi-Node Broadcast only after writing the delivery, duplicate and partition assumptions. Preserve protocol histories rather than relying on a success banner.
- MIT 6.5840 - MapReduce, RPC and consistency bridge Use the introductory MapReduce, RPC, GFS and consistency lectures after the local RPC and store gates. The MapReduce lab is optional. Do not begin Raft or sharded KV as foundation work.
- Apache Kafka documentation - design Read Persistence, The Consumer (Consumer Position), Message Delivery Semantics, Using Transactions, Replication and Log Compaction for a concrete log: offsets, consumer positions, the at-most-once, at-least-once and exactly-once boundaries, in-sync replicas and compaction guarantees. Map each guarantee onto your own log before trusting it.
- Building Distributed Systems from Scratch - one challenge path Choose one messaging, durable-log or partitioning challenge that matches a failed checkpoint. State the model, failures and evidence independently because interactive grading behavior has not been verified.
- AlgoMaster System Design - distributed fundamentals slice Use Database Replication, Consistency Models, Logical Clocks, Vector Clocks, Network Partitions, Split Brain Problem, Leader Election, Database Partitioning, Consistent Hashing, Delivery Semantics, Dead Letter Queues, Idempotency, Two-Phase Commit (2PC), Outbox Pattern and Streaming Engines as bounded review after DDIA. Attempt only the exercise that matches your implemented history, then challenge its assumptions with a node-loss, delay or duplicate case.