Ordering without real clocks
Physical clocks on different machines drift, so they cannot reliably order events. Lamport timestamps give a logical ordering using only a counter per process and the messages already being exchanged.
The two rules
Each process keeps an integer counter.
- Before any local event or before sending a message, increment the counter.
- On receiving a message, set the counter to max of local and received, then increment.
This guarantees that if event A happens before event B, then the timestamp of A is less than the timestamp of B. The implication runs one way only.
The limitation
The reverse is not true. A smaller timestamp does not prove a happens before relationship, because two unrelated events on different processes can get unrelated numbers. Lamport clocks give a consistent total order when ties are broken by process id, but they cannot detect whether two events are truly concurrent.
Key idea
Lamport timestamps order events with a per process counter so that cause has a smaller value than effect, but they cannot tell whether two events are concurrent.