Total order is not causality
Total order is not causality
sorted stamps decide display order, only messages decide happened-before
the exchange, sorted with pid tie-break
(1,A)
A posts, c 0 to 1
(1,C)
C posts, B adopts 1
(2,B)
B replies, c 1 to 2
total order: (1,A) < (1,C) < (2,B) — good for sorting, says nothing about cause
the trap: two events, zero messages
event x on A
stamped (5,A)
no message in or out
event y on C
stamped (3,C)
no message in or out
no path
either way
(3,C) < (5,A) in stamps, yet neither caused the other — concurrency is invisible
Lamport rule: send ticks +1, receive adopts max — the clock never moves backwards
price of truth about concurrency: vector clocks, one entry per process
legend: violet = message exchange, rose = message-free trap, yellow = the rule and its price