# DDIA Ch. 10: a Lamport timestamp orders two concurrent events; a vector clock refuses ## Concept A **Lamport timestamp** is one integer per event (plus a node id to break ties). It buys a **total order**, and that order is safe in exactly one direction: if `a` happened-before `b`, then `L(a) < L(b)`. The reverse is a trap. Run a Lamport clock and a **vector clock** over the *same* event log and you find a pair of events `e9` and `e4` with `L(e9) = 3 < 4 = L(e4)` — which begs the reader to conclude "`e9` happened before `e4`" — that were in fact **concurrent**: no message path connects them, neither causally precedes the other. The vector clock stamps them `[0,0,3]` and `[2,2,0]`, *neither dominates the other*, and reports **concurrent**. Then watch the mechanism: strip Lamport's **max-on-receive** rule and even the one-way guarantee collapses — a message received at `e3` gets timestamp **1** though it was sent at `e2` with timestamp **2**, so the effect now looks *earlier* than its cause. This exercise is the counterpart to Ch. 6's [version-vectors](../ch06/version-vectors.md), which uses per-process counters to *detect* conflicting sibling writes. There the angle was conflict detection; here it is the **total-order illusion** — a single integer that reads like causality but isn't — and the **max-on-receive** mechanism that a Lamport clock rests on. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 10 — *Consistency and Consensus*, §"Lamport timestamps / hybrid logical clocks versus vector clocks." The book's claim, tightly paraphrased: Lamport timestamps give a total order consistent with causality — `a → b` implies `L(a) < L(b)` — but from a Lamport timestamp alone **you cannot tell whether two events are concurrent or causally ordered**; only a vector clock (one entry per node) distinguishes the two. Here you build both over one log and watch exactly that gap open. ## Prerequisites The surprise turns on a *one-directional* implication. Each line notes where the idea shows up in the run. 1. **Happens-before and concurrency** — `a → b` ("a happened-before b") holds if a is earlier on the same process, or a is a send and b its receive, or by transitivity. Two events are **concurrent** when *neither* `a → b` nor `b → a`. It shows up as `e9` and `e4`: no chain of process-steps or messages links them. Concurrency is about the *absence of a causal path*, not about wall-clock simultaneity. **(carries the result)** 2. **Lamport clock — total order, one-directional guarantee** — one integer per event; on receive, `L = max(local, message) + 1`. It totally orders all events and guarantees `a → b ⇒ L(a) < L(b)`. It shows up as the `Lamport` column. The one-way part is the whole trap. **(carries the result)** 3. **Vector clock — partial order, detects concurrency** — one counter per process; `V(a) ≤ V(b)` componentwise iff `a → b`, so *incomparable* vectors mean *concurrent*. It shows up as the `vector [P1,P2,P3]` column and the `dominates` check. 4. **Max-on-receive** — the receive rule takes the componentwise/scalar MAX with the incoming timestamp before incrementing. It shows up in the mechanism demo: drop it and a receive can be stamped below its send. 5. **The one-way implication** — `a → b ⇒ L(a) < L(b)` is true; its converse `L(a) < L(b) ⇒ a → b` is **false**. It shows up as `L(e9) < L(e4)` on *concurrent* events. **(carries the result)** ### Where to learn the prerequisites - **Happens-before, Lamport clocks, max-on-receive (#1, #2, #4):** Lamport, *Time, Clocks, and the Ordering of Events in a Distributed System* (1978) — the source of the clock condition and the receive rule. - **Vector clocks (#3):** Fidge (1988) and Mattern (1988); DDIA §"Detecting Concurrent Writes" and the companion [version-vectors](../ch06/version-vectors.md) exercise, which applies the same partial order to sibling detection. - **The one-way implication (#5):** DDIA §"Lamport timestamps" — a Lamport timestamp is consistent with causality but *loses* it; you cannot invert the total order back into happens-before. If only one is new, make it **#2 + #5 together**: *Lamport is one-directional.* The clock guarantees ordered-if-causal, never causal-if-ordered. ## Environment Deterministic — the event log is fixed, so every timestamp reproduces exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker - No real concurrency or network: three processes and their messages are one fixed list, replayed in a single causal order, so the stamps are identical every run ## Mental model Both clocks watch the *same* ten events; only the stamp differs. - **Lamport timestamp** — a single number that guarantees causally-related events come out ordered (`a → b ⇒ L(a) < L(b)`) but says *nothing* about events that aren't related. Two concurrent events still get two different numbers, and the smaller one is **not** "earlier" in any causal sense — it just lost the tie. The integer has one slot; it cannot record *which process knew what*, only a running high-water mark. - **Vector clock** — one counter per process, so the stamp carries per-process knowledge. `V(a) ≤ V(b)` in every component means everything `a` knew, `b` knew too → `a → b`. If each vector has a component the other lacks, neither knew the other → **concurrent**. Domination = causality; incomparability = concurrency. The event log (three processes, two messages): ``` P1: e1 local --- e2 send(m1) ---------------------------------. \ | P2: e3 recv(m1) - e4 local - e5 local - e6 send(m2) \ P3: e7 local - e8 local - e9 local ----------------------- e10 recv(m2) ``` There is **no** message path from P3's local run (`e7, e8, e9`) to P2's local run (`e4, e5`) — those events are genuinely concurrent. Everything is one script, `code/lamport_vs_vector_clocks.py`. ## Setup ``` cd study/ddia/ch10 python3 code/lamport_vs_vector_clocks.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — stamp every event with both clocks **Predict.** Walk the log with both rules. Lamport: `local`/`send` do `L += 1`; `recv` does `L = max(local, message) + 1`. Vector: bump your own component, and on receive take the componentwise max first. `P3` does three local events (`e7, e8, e9`) before receiving `m2`. What Lamport timestamp does `e9` get? What vector? **Observe.** ``` ========================================================================== ONE event log, two clocks: Lamport timestamp vs vector clock ========================================================================== P1: e1 local, e2 send(m1) P2: e3 recv(m1), e4 local, e5 local, e6 send(m2) P3: e7 local, e8 local, e9 local, e10 recv(m2) (no message path from P3's e7/e8/e9 to P2's e4/e5) event proc kind Lamport vector [P1,P2,P3] ----- ---- --------- ------- ----------------- e1 P1 local 1 [1,0,0] e2 P1 send(m1) 2 [2,0,0] e3 P2 recv(m1) 3 [2,1,0] e4 P2 local 4 [2,2,0] e5 P2 local 5 [2,3,0] e6 P2 send(m2) 6 [2,4,0] e7 P3 local 1 [0,0,1] e8 P3 local 2 [0,0,2] e9 P3 local 3 [0,0,3] e10 P3 recv(m2) 7 [2,4,4] ``` `e9` is `P3`'s third local event, so it climbs `P3`'s own counter to Lamport **3** and vector **[0,0,3]** — a stamp that knows nothing of `P1` or `P2`. `e4` sits on `P2` at Lamport **4**, vector **[2,2,0]** — it has already absorbed `m1` from `P1`. ### Step 2 — the pair Lamport puts in a false order **Predict.** Compare `e9` (Lamport 3) and `e4` (Lamport 4). Lamport says `3 < 4`. Is `e9` actually *happened-before* `e4`? Check the vectors: does either `[0,0,3]` or `[2,2,0]` dominate the other componentwise? **Observe.** ``` -------------------------------------------------------------------------- THE TRAP: a concurrent pair that Lamport puts in a total order -------------------------------------------------------------------------- e9: [0,0,3] Lamport = 3 (P3 local) e4: [2,2,0] Lamport = 4 (P2 local) Lamport says L(e9) = 3 < 4 = L(e4) -> tempting (WRONG) reading: 'e9 happened before e4'. Vector clock: [0,0,3] vs [2,2,0] e9 <= e4? no (e9[P3]=3 > 0=e4[P3]) e4 <= e9? no (e4[P1]=2 > 0=e9[P1]) neither dominates -> vectors report: CONCURRENT Verdict: 'e9 before e4' is FALSE. They are concurrent. Lamport's single integer cannot tell 'earlier' from 'concurrent'; the vector can. ``` `L(e9) < L(e4)` is real, but it does **not** mean `e9 → e4`. `e9` knows `P3` did 3 steps (`[_,_,3]`) and nothing of `P2`; `e4` knows `P2` did 2 steps *and saw `P1`* (`[2,2,_]`) and nothing of `P3`. Each vector has a component the other lacks → neither happened-before the other → **concurrent**. Lamport's `3 < 4` is a tie-break, not a causal fact. ### Step 3 — the causal pair where both clocks agree **Predict.** Now take `e2` (send `m1`) and `e3` (receive `m1`). A send always happens-before its receive, so this pair *is* causal. Will Lamport order them the same way, and will the vector for `e3` dominate the vector for `e2`? **Observe.** ``` -------------------------------------------------------------------------- THE CONTRAST: a causal pair (m1 send -> recv) where BOTH agree -------------------------------------------------------------------------- e2: [2,0,0] Lamport = 2 (send m1) e3: [2,1,0] Lamport = 3 (recv m1) Lamport: L(e2) = 2 < 3 = L(e3) -> ordered e2 before e3 Vector: [2,1,0] dominates [2,0,0] -> e2 -> e3 (causal) Here the total order is RIGHT: e2 really did happen-before e3. (Lamport is safe one way: a -> b => L(a) < L(b). The trap above is the converse, which does not hold.) ``` When the pair really is causal, both agree — `L(e2) < L(e3)` **and** `[2,1,0]` dominates `[2,0,0]`. That is the one-way guarantee working: `a → b ⇒ L(a) < L(b)`. The trap in Step 2 was the *converse*, `L(a) < L(b) ⇒ a → b`, which is false. ### Step 4 — drop max-on-receive and even the one-way rule breaks **Predict.** Recompute Lamport with the receive rule changed to a plain `L += 1` — the receiver ignores the message's timestamp. Message `m1` is sent at `e2` (Lamport 2) and delivered to `e3`, which is `P2`'s *first* event. Without max-on-receive, what timestamp does `e3` get — and is `L(e2) < L(e3)` still true? **Observe.** ``` -------------------------------------------------------------------------- THE MECHANISM: why max-on-receive is the minimum for even the one-way rule -------------------------------------------------------------------------- Message m1: sent at e2 (on P1), received at e3 (on P2). Since the send causes the receive, e2 -> e3, so the one-way guarantee REQUIRES L(e2) < L(e3). BROKEN rule (recv just does L += 1, ignoring the message): L(e2) = 2 L(e3) = 1 -> 2 >= 1 VIOLATION: receive <= send P2's first event e3 is stamped 1, but the message it delivered was sent at Lamport 2. The effect looks EARLIER than its cause -- the one thing Lamport promises is broken. FIXED rule (recv does L = max(L, msg) + 1): L(e2) = 2 L(e3) = 3 -> 2 < 3 ok: receive > send, guarantee restored max-on-receive drags the receiver's counter past the message's timestamp, so no receive can ever undercut its send. ``` Without max-on-receive, `P2`'s counter knows only its own history — one step — so `e3` gets **1**, though the message it delivered was sent at **2**. Now `L(e2) = 2 > 1 = L(e3)`: the receive is stamped *below* its send, so the effect reads as earlier than its cause. `max(local, message) + 1` is the minimum fix — it forces the receiver past the message's timestamp — and `e3` becomes **3 > 2**. ## What you should see - Ten events stamped by both clocks; `e9` = Lamport **3** / **[0,0,3]**, `e4` = Lamport **4** / **[2,2,0]**. - **The trap:** `L(e9) = 3 < 4 = L(e4)`, yet the vectors are **incomparable** — the pair is **concurrent**, so "e9 before e4" is false. - **The contrast:** the causal pair `e2 → e3` (send/recv of `m1`) — Lamport `2 < 3` **and** `[2,1,0]` dominates `[2,0,0]`; both agree. - **The mechanism:** drop max-on-receive and `m1`'s receive `e3` is stamped **1** below its send `e2` at **2** — the one-way guarantee violated. The MAX rule restores `e3 = 3 > 2`. ## Why Start from the guarantee Lamport actually gives. Every event advances a counter, and a receive takes `max(local, message) + 1`, so any event on the causal path from `a` to `b` — same-process successors, and receives of `a`'s messages — is forced strictly higher than `a`. By transitivity `a → b ⇒ L(a) < L(b)`. That is real and it is all Lamport promises. The converse fails because the guarantee is a projection that throws away information. A single integer is a **high-water mark**: it records *the length of the longest causal chain leading to this event*, and nothing about *which processes* contributed to that chain. `e9`'s counter reached 3 purely from `P3`'s own local steps; `e4`'s reached 4 from `P2`'s steps plus the `m1` it absorbed from `P1`. Two different chains, two different lengths — and `3 < 4` compares the lengths, not the causality. When two events lie on *unrelated* chains (no message ever flowed between their branches), Lamport still hands back two numbers, and one is smaller. The order is *consistent* with causality (it never contradicts a real `a → b`) but not *faithful* to it (it invents an order where none exists). A vector clock keeps exactly the discarded piece: one component per process, so the stamp says *how much of each process's history this event has seen*. `a → b` holds iff `b` has seen at least as much of **every** process as `a` — i.e. `V(a) ≤ V(b)` in all components. Concurrency is then visible directly: if `a` has seen more of some process than `b`, and `b` more of another, then a causal path *cannot* exist in either direction (a path would have carried the counts along), so the vectors are incomparable and the events are concurrent. That is why the vector can *detect the absence of a causal path* and the integer cannot — the integer summed the per-process knowledge into one number and lost the ability to ask "did `b` know everything `a` knew?" The mechanism demo isolates why max-on-receive is not optional. The only way a send can influence the receiver's counter is for the receive to *read* the message's timestamp; a bare `L += 1` leaves the receiver advancing on its own local history alone. If that history is shorter than the sender's — and `P2`'s first event has history length 0 — the receive lands *below* the send, and the lone guarantee `a → b ⇒ L(a) < L(b)` is gone. `max(local, message)` is the minimum coupling: it pulls the receiver up to at least the message's height before the `+1`, so no receive can ever undercut its send. ### The boundary — when the integer is enough You need vectors only when you must **detect concurrency or conflicts**. If all you need is *some* total order everyone agrees on — a tie-break key, a deterministic sort, **total-order broadcast** where every node must deliver messages in the same sequence — a Lamport timestamp (integer + node id) is exactly right and far cheaper than an O(nodes) vector. The catch it hides is precisely the one this exercise exposes: that agreed order will silently linearize events that were concurrent, so never read `L(a) < L(b)` back as "a caused b." Reach for a vector clock the moment the *question* is "were these concurrent?" — sibling detection, conflict resolution, causal consistency — and for a plain Lamport clock when the question is only "give me one order we all share." ### Go deeper 1. **Cross-check against Ch. 6.** The [version-vectors](../ch06/version-vectors.md) exercise runs the *same* partial-order logic to keep shopping-cart siblings. Confirm that the incomparability test here (`neither dominates`) is the identical rule that flags `[milk]` and `[eggs]` as concurrent there — one mechanism, two uses (ordering vs conflict detection). 2. **From total order to consensus.** A Lamport clock gives a total order, but only *after the fact* — nodes still disagree on the order until they exchange everything. Total-order broadcast (every node delivers the same messages in the same order, *as they arrive*) turns out to be **equivalent to consensus**: build one and you can build the other. Trace why the "as they arrive" is the hard part the offline Lamport clock sidesteps. 3. **Prune the vectors.** Vector clocks cost one integer per process and grow with the cluster. Look at how *hybrid logical clocks* (HLCs) and *interval tree clocks* try to recover most of the concurrency-detection power at closer to Lamport's size — and where they give ground. ```