Message Ordering
Lamport Happened Before Relation
Each processor orders by local time
A send precedes the receive
Transitivity
This is the only observable order existing in Distributed Systems
It captures causality: if a happened before
b then a can be a cause of b
Lamport Clocks
Each processor keeps a local counter (incrementing)
Sending a message adds the counter as a timestamp
Upon reception of a message, my counter gets the
max between local counter and timestamp
if a happened before b then
time(a) less than time(b)
- 42 -