Lamport clocks

Often you don't need to know when something happened. You need to know whether one event could have influenced another. In 1978, Leslie Lamport showed that you can track that with simple counters, with no physical clock at all. The result is the Lamport clock.

The big idea

Each process keeps one counter. Every event bumps it. Every message carries the counter. When a message arrives, the receiver jumps its counter past the sender's value. The counter then reflects the cause-and-effect chain.

Think of the date stamp on a letter. A reply must carry a later date than the letter it answers. A date that jumps forward on receipt keeps replies later than what they reply to.

Walking through it

The rules are three lines.

1. Before each local event or send, L = L + 1.
2. Attach L to every message sent.
3. On receive with timestamp T, set L = max(L, T) + 1.

This guarantees one thing: if a → b, then L(a) < L(b).

Three processes trace the same numbers as the diagram below. P1 does an event a and sends m1 to P2. P2 does c, receives m1, and sends m2 to P3. P3 does e, receives m2, and sends m3 back to P1.

P1: a      L = 0 + 1 = 1
P1: send   L = 1 + 1 = 2           (m1 carries 2)
P2: c      L = 0 + 1 = 1
P2: recv   L = max(1, 2) + 1 = 3
P2: send   L = 3 + 1 = 4           (m2 carries 4)
P3: e      L = 0 + 1 = 1
P3: recv   L = max(1, 4) + 1 = 5
P3: send   L = 5 + 1 = 6           (m3 carries 6)
P1: recv   L = max(2, 6) + 1 = 7

For a total order, where every pair of events is ranked, break ties by process ID. Compare (L, process ID). Events a, c and e all have L = 1, so the order is a < c < e.

The limit. The converse doesn't hold. L(a) < L(b) does not mean a → b. In the trace, e has L = 1 and b, the send of m1, has L = 2. So Lamport order puts e first, yet the two are concurrent. P1 never heard from P3 before it sent m1. Lamport clocks give an order consistent with causality. They can't tell you whether two events were concurrent. For that, read about vector clocks.

Common mistakes

• Reading the number as causality. A smaller counter doesn't prove the event came first in cause and effect.
• Forgetting the max on receive. Without it, the receiver's counter can fall behind the message and break the ordering.
• Expecting real time. Lamport numbers count events. They say nothing about seconds.

Check yourself

1. Lamport says e (L = 1) comes before b (L = 2). Are they causally related? No. They're concurrent. Lamport order is consistent with causality, but it doesn't prove a causal link.
2. What must a receiver do with a message's counter? Set its own counter to the larger of the two values, then add one.

Key takeaways

• A Lamport clock is a counter that bumps on events and jumps past received messages.
• It gives a total order that never contradicts cause and effect.
• It can't say whether two events were concurrent. Use vector clocks for that.

Further learning

Lamport's 1978 paper introduced the idea, and it's short and readable.

Next, read about vector clocks, which can detect concurrent events.