Causality & the happened-before relation

Click any two of the same nine events from last chapter. Some pairs are linked by an actual chain of messages — one genuinely could have influenced the other. Others have no such chain at all: neither could possibly know the other happened.

Two events are related by happened-before exactly when one vector clock dominates the other:

If neither $a \le b$ nor $b \le a$ holds, the events are concurrent — genuinely unordered, not just unordered-so-far.

• $a, b$ — two events' vector clocks.
• $a \to b$ — "$a$ happened-before $b$": a real chain of messages (or shared-process order) links them.

1. Why vector clocks get this exactly right

   A vector clock's $i$-th component counts how many of process $i$'s events the current event's process has learned about, through some chain of messages. Domination in every component means "everything $a$ knew about, $b$ also knew about, and then some" — the definition of a causal chain.

2. Why a Lamport number can't do the same job

   A Lamport timestamp collapses that whole vector into one number. Two genuinely concurrent events can still end up with different numbers, because the collapsing throws away exactly the structure that distinguished "definitely before" from "no relation."

Pick two events and watch both readouts at once: the causal relation (from vector clocks) and whether Lamport's numbers would have implied an order that the causal relation doesn't actually support — lamportFalselyOrders.

Compare e3 (P0's third event) against e6 (P2's first event), then contrast with a genuinely causal pair.

1. e3 and e6's vectors

   P0's own chain, bumping only its own component each step:

   • e1: $[0,0,0]\to[1,0,0]$
   • e2 (sends m1): $[1,0,0]\to[2,0,0]$
   • e3: $[2,0,0]\to[3,0,0]$

   P2's e6 is its first event, starting from the zero vector and bumping only its own component:

   • e6: $[0,0,0]\to[0,0,1]$

   So e3 = [3, 0, 0], e6 = [0, 0, 1]. Neither dominates the other — the third component of e3 is 0 but e6's is 1; the first component of e6 is 0 but e3's is 3. Concurrent.

2. Yet Lamport disagrees

   Lamport's rule bumps the same process's scalar counter by 1 per event:

   • P0's counter: $1$ (e1), $2$ (e2), $3$ (e3) → LAMPORT(e3) = 3
   • P2's counter, starting fresh: $1$ (e6) → LAMPORT(e6) = 1

   Different numbers, for a pair with no causal relationship at all. That's the "false order": Lamport's scalar clock can't represent "unrelated," so it just picks some order.

3. Contrast: e2 and e7

   • e2 = [2, 0, 0] (P0's send, from the chain above)
   • e7 (P2 receives m2, sent by e5 with vector $[2,2,0]$): take the componentwise max of P2's own vector at that point ($[0,0,1]$, from e6) with the incoming $[2,2,0]$, giving $[2,2,1]$, then bump P2's own component: $[2,2,2]$

   Every component of e2 is $\le$ the matching component of e7, and they're not equal — a real causal chain: e2 sends m1, P1 receives it and sends m2, P2 receives m2 at e7. Lamport's numbers (2 and 5, the latter from $\max(1,4)+1$ against m2's stamped timestamp of 4) happen to agree with this order too — but that agreement isn't guaranteed the way it is for a concurrent pair.