A Lamport clock is one counter per process and one rule: L(e) = max(L_local, L_msg) + 1. It produces a total order that never contradicts causality — if a happened before b then L(a) < L(b) — and the converse is false. On an eleven-event diagram there are 32 ordered pairs and 17 further pairs whose stamps are ordered while the events are not, which is exactly the gap the next lesson closes.
Core ideas
The rule has three cases, the guarantee has one direction, and the counterexample is on the same diagram you stamped.
Each process keeps one integer. On a local event it increments it. On a send it increments and attaches the new value to the message. On a receive it takes the maximum of its own counter and the one on the message, then increments. The max is what carries information across processes, and the + 1 is what keeps the stamp of the receive strictly after the send.
If a happened before b — by process order, by a message, or by a chain of those — then L(a) < L(b), because every step of the chain strictly increases the stamp. That is the guarantee and it is genuinely useful: sorting by L, with process identifiers breaking ties, gives a total order that never puts an effect before its cause.
The converse fails and it fails often. On this diagram L(B1) = 1 and L(A2) = 2, yet no chain of process order and messages runs from B1 to A2 — they are concurrent. There are 17 such pairs here. What L(a) < L(b) does rule out is b → a, by the contrapositive of soundness, and that is all it rules out.
The material
How the counters propagate along a diagram, what the resulting order promises, and a pair of events it gets the wrong way round.
Event a happens before b, written a → b, if they are on the same process and a is earlier, or a is the send of a message whose receive is b, or there is a chain of such steps from a to b. The Lamport timestamp L assigns each event max(L_local, L_msg) + 1, where L_msg is the stamp carried by a received message and is absent otherwise.
Happens-before is a partial order, not a total one: it is the transitive closure of “same process, earlier” and “sent, then received”, and any two events not connected by such a chain are unrelated by it. A Lamport clock takes that partial order and produces integers consistent with it.
The third receive is the instructive one. The message from C1 carries the stamp 1, which is smaller than A's own counter at that point, so the local clock wins the maximum and A4 becomes 4 rather than 2. A reader who adds one to the message stamp instead of to the maximum gets a stamp that violates A's own process order, which is the first thing to check when a diagram comes out wrong.
Seventeen against thirty-two is not a rare corner case, it is a third of the ordered-looking pairs on a small diagram. A Lamport stamp is a one-dimensional summary of a partial order, and the information it cannot carry is exactly the information about which pairs are unrelated.
Break ties by process identifier and the stamps give a total order on all events, consistent with causality. That is enough for a distributed mutual-exclusion queue, for a deterministic replay of a log, and for any rule of the form “process requests in a fixed order that everyone agrees on”. What it is not enough for is detecting that two updates were concurrent, because the total order cheerfully orders pairs that nothing ordered — and a merge that trusts it will silently pick a winner between two updates that should both have been kept.
So the honest summary is: Lamport stamps are a cheap way to get an order everyone agrees on, and a wrong way to decide whether one event caused another. One integer per process is all they cost and it is also all they can carry. “Vector Clocks and Concurrency” spends n integers instead and gets the missing direction back.
Interactive
A total order consistent with happens-before — and only one way round
Method
Draw first, stamp second. Most errors in this arithmetic are errors about which edges exist, not about the maximum.
One horizontal line per process, events as dots along it in order, an arrow from each send to its receive. Everything that follows reads off this picture, and a missing arrow is invisible in a list of stamps.
An event can be stamped once every event with an edge into it has been. Going left to right on each process, deferring a receive until its send is stamped, is enough.
Local event: L + 1. Send: L + 1, and put that value on the message. Receive: max(own L, message L) + 1. The commonest slip is adding one to the message's stamp rather than to the maximum, which breaks process order whenever the local clock was ahead.
Pick two events on different processes with different stamps and try to trace a chain from the smaller to the larger. If you cannot, you have found one of the pairs where the total order is inventing an order — and knowing that such pairs exist is the point of the exercise.
Three processes, eleven events, three messages. The stamps are mechanical; the interesting part is the last third of the page, where a pair of stamps says something the diagram does not support.
The stamps are correct and the guarantee holds in the direction it claims: every message is stamped so that the receive is strictly after the send, and every process's own events increase. Sorting all eleven by stamp, with ties broken by process name, gives an order no observer could prove wrong.
And B1 before A2 is a fiction that order contains. Both are first or second events on their own processes, neither has heard of the other, and the stamps nonetheless place one before the other because integers are totally ordered and the events are not. Seventeen of the pairs here are like that.
For a faded rehearsal, add a fourth message A3 → C3 to the diagram. The supplied first move is that C3 is now a receive rather than a local event, so its stamp becomes max(L(C2), L(A3)) + 1. Restamp every event that changes, say whether the number of false pairs should rise or fall and why, then check both against the lab.
You should be able to apply the three cases of the rule without hesitation, check soundness along every message, produce a total order by breaking ties on process identity, and exhibit two concurrent events whose stamps are nevertheless ordered.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.