Lamport Clocks and Happens-Before

Ordering without physical time

Leslie Lamport defined happens-before (written a -> b): a -> b if a and b are on the same process and a came first, or if a is the sending of a message and b is its receipt, or transitively through a chain of such steps. If neither a -> b nor b -> a, the events are concurrent: no information could have flowed between them. A Lamport clock is a counter per process with three rules: increment before each local event, attach the counter to every message sent, and on receipt set the counter to max(local, received) + 1. This guarantees that if a -> b then L(a) < L(b). The converse does not hold: a smaller Lamport timestamp does not prove happens-before. Breaking ties by process id turns Lamport timestamps into a total order that every node can compute identically.

Tracing a Lamport clock

Follow the counters as A does a local event, sends a message, and B receives it after its own local event.

class Process:
    def __init__(self, name):
        self.name, self.clock = name, 0

    def local_event(self):
        self.clock += 1
        return self.clock

    def send(self):
        self.clock += 1
        return self.clock            # timestamp travels with the message

    def receive(self, msg_ts):
        self.clock = max(self.clock, msg_ts) + 1
        return self.clock

a, b = Process("A"), Process("B")
a.local_event()                      # A: 1
t = a.send()                         # A: 2, message carries 2
b.local_event()                      # B: 1
print("B receives at", b.receive(t)) # max(1, 2) + 1 = 3
print("clocks:", a.clock, b.clock)

Output:

B receives at 3
clocks: 2 3

1. Line 17: Both processes start with clock 0.
2. Line 18: A local event: increment first, so A becomes 1.
3. Line 19: Sending is also an event: A ticks to 2 and the message carries timestamp 2.
4. Line 20: B has its own unrelated event and ticks to 1. It is concurrent with A's events so far.
5. Line 14: On receipt B takes max(1, 2) + 1 = 3, so the receive is ordered after the send.
6. Line 21: The receive timestamp 3 is printed.
7. Line 22: Final clocks: A=2, B=3.

Token numbers at a bank

Counters at a bank branch each hand out token numbers. When a customer walks from one counter to another, the second counter bumps its number past the customer's token. Tokens then never go 'backwards' along any customer's path, even though counters never compare watches.

Quick check: If Lamport timestamps satisfy L(a) < L(b), what can you conclude?

• a happened before b
• a and b are concurrent
• b happened before a
• b did not happen before a, but a and b may be concurrent