The Algorithm
Leslie Lamport invented a simple mechanism to assign numbers to events such that the happened-before relationship is preserved. Each process maintains a single integer counter, called its Lamport Clock.
The rules are:
- Initialize: Every process starts with clock value
0. - Internal event: Before executing an internal event, the process increments its clock:
clock = clock + 1. - Send event: Before sending a message, the process increments its clock and attaches the current value to the message:
clock = clock + 1; send(message, clock). - Receive event: Upon receiving a message with timestamp
T, the process updates its clock:clock = max(clock, T) + 1.
The max in rule 4 is the key. It ensures the receiver's clock is always greater than both its own previous value and the sender's value at the time of sending. This guarantees that the receive event has a higher timestamp than the send event.
What Lamport Timestamps Guarantee
If A → B (A happened before B), then timestamp(A) < timestamp(B). This is the clock consistency condition.
However, the converse is not guaranteed. If timestamp(A) < timestamp(B), you cannot conclude that A → B. They might be concurrent events that just happened to get low and high numbers respectively.
This is the critical limitation: Lamport timestamps can confirm causality but cannot rule it out. They give you a total order (every event gets a unique number), but that order may not reflect true causality for concurrent events.