Lesson 21 · Time, order and truth · Module 3

Happens-Before

Lesson 20 took the wall clock away. What replaces it is not a better clock — it is a different kind of order, one that admits it cannot rank every pair of events. That admission is the whole idea, and once you have it, half the confusing behaviour in a distributed system stops being confusing.

The win in this lesson: given any two events, you will be able to say whether one could have caused the other or whether they are genuinely concurrent — and you will know that "concurrent" is a real category, not a failure to measure carefully enough.

1. The clock is gone. Now what?

The previous lesson ended somewhere uncomfortable: even with NTP running everywhere, you cannot order two events on two machines by comparing their timestamps.

"The clock synchronisation performed by NTP and similar protocols always leaves some residual uncertainty about the exact skew between two clocks, especially if the network latency in the two directions is asymmetric."

Martin Kleppmann, Distributed Systems lecture notes (Cambridge, 2021–22), §3.3 Causality and happens-before

So a reply can carry an earlier timestamp than the message it answers. The instinct is to ask for better clocks. The better question is: what do we actually need the clock for? Usually the answer is "to know whether this event could have influenced that one" — and that question has an exact answer which needs no clock at all.

2. Three rules, and an order with holes in it

An event is one thing happening at one node: a local step, a send, or a receive. We write a → b for "a happens before b". Three rules, and nothing else:

1. Same node. If a and b happened at the same node and a came first in that node's local execution order, then a → b.
2. A message. If a is the sending of a message and b is the receipt of that same message, then a → b.
3. Transitivity. If a → c and c → b, then a → b.

Now the consequence that matters. Take the transitive closure of those three rules and you do not get a ranking of all events. You get an order with holes in it:

"This is a partial order, which means that it is possible that for some events a and b, neither a happened before b, nor b happened before a. In that case, we call a and b concurrent."

Kleppmann, Distributed Systems notes, §3.3

"Note that here, 'concurrent' does not mean literally 'at the same time', but rather that a and b are independent in the sense that there is no sequence of messages leading from one to the other."

Kleppmann, Distributed Systems notes, §3.3

Lamport's original paper opens on exactly this point, and on why people keep tripping over it:

"In a distributed system, it is sometimes impossible to say that one of two events occurred first. The relation 'happened before' is therefore only a partial ordering of the events in the system. We have found that problems often arise because people are not fully aware of this fact and its implications."

Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", CACM 21(7), 1978 · Introduction

3. A counter that respects causality

Happens-before is a definition, not a mechanism: a node cannot see the whole diagram. A Lamport clock is the cheapest thing that lets each node carry enough of it around — one integer.

"A Lamport timestamp is essentially an integer that counts the number of events that have occurred. As such, it has no direct relationship to physical time."

Kleppmann, Distributed Systems notes, §4.1 Logical time

on initialisation do
    t := 0                    -- each node has its own local variable t
end on

on any event occurring at the local node do
    t := t + 1
end on

on request to send message m do
    t := t + 1
    send (t, m) via the underlying network link
end on

on receiving (t', m) via the underlying network link do
    t := max(t, t') + 1
    deliver m to the application
end on

In words, the two lines that carry the whole scheme:

"When a message is sent over the network, the sender attaches its current Lamport timestamp to that message. […] When the recipient receives a message, it moves its local Lamport clock forward to the timestamp in the message plus one; if the recipient's clock is already ahead of the timestamp in the message, it is only incremented."

Kleppmann, Distributed Systems notes, §4.1

Run it on the same three nodes and annotate every event with the counter value it produced:

The property you bought for that one integer:

"Lamport timestamps have the property that if a happened before b, then b always has a greater timestamp than a; in other words, the timestamps are consistent with causality."

Kleppmann, Distributed Systems notes, §4.1

4. What the counter refuses to tell you

The implication runs one way only, and this is the single thing to memorise:

"However, the converse is not true: in general, if b has a greater timestamp than a […] we do not know whether it is the case that a → b or that a ‖ b."

Kleppmann, Distributed Systems notes, §4.1

Row two is where systems get hurt. A single integer cannot distinguish "this write came after that one" from "these two writes never heard of each other", so any system that resolves conflicts by comparing Lamport timestamps resolves concurrency as if it were succession:

"[W]e get what is known as last writer wins (LWW) semantics: the update with the greatest timestamp takes effect, and any concurrent updates with lower timestamps to the same key are discarded."

Kleppmann, Distributed Systems notes, §6.2

The residual risk, named

A Lamport clock gives you a causal order and silent data loss on concurrent writes. Whether that trade is acceptable is an application question — for a counter of page views it is fine, for a shopping basket it is not. What it is not is a bug you can tune away, because the information was never in the integer:

"Given the Lamport timestamps of two events, it is in general not possible to tell whether those events are concurrent or whether one happened before the other. If we do want to detect when events are concurrent, we need a different type of logical time: a vector clock."

Kleppmann, Distributed Systems notes, §4.1

That is Lesson 22.

5. Check yourself

6. Back to your world

The next time two services disagree about which update is newer, stop looking at the timestamps and ask the structural question instead: did a message pass between these two writes? If yes, there is a real order and you should be preserving it. If no, they are concurrent, and whatever order your system picked was arbitrary — you have a conflict, and you are either resolving it or losing one side of it silently.

The concrete habit: when you propagate a write, propagate the context it was made in. A write that carries no record of what its author had already seen cannot be merged later, only overwritten.