Lamport Timestamps

Introduction

The last lesson left you with a shopping list. Happened-before answers the right question, but as defined it's a graph walk — nobody traverses a message graph on the write path. You were promised a number: something each machine can carry, stamp on every event, and compare in one instruction. A number that encodes the arrows.

Leslie Lamport's 1978 paper delivers it, and the delivery is almost insultingly small. No coordination, no extra messages, no clock hardware: one integer per machine and one habit: when a message arrives, catch up. This lesson counts the promised nine lines, proves what the number guarantees, and then spends real time on the part that bites people in production: what the number quietly throws away.

The whole Lamport mechanism in one journey. Machine A wears its counter as an amber badge reading 5. An envelope slides down the message arrow toward machine B with the stamp 5 riding above it. Machine B knew only 2 — its old badge is struck through in red. The dark arithmetic panel does the one move that makes the clock work: max(2, 5) + 1 = 6. Foot band: the message carries before-ness, and the receiver absorbs it

Nine Lines, Counted

One integer per machine. Three habits:

Tick before every local event so the counter goes up by one.
Sends carry the counter: tick, then attach the value to the message.
Receives catch up — take the larger of what I knew and what the message brought, add one, and that's the receive's stamp.

As promised, nine lines. Count them:

class LamportClock:                      # 1
    t = 0                                # 2  one integer per machine
    def tick(self):                      # 3  before every local event
        self.t += 1                      # 4
    def send(self):                      # 5
        self.tick(); return self.t       # 6  the stamp rides the message
    def receive(self, stamp):            # 7
        self.t = max(self.t, stamp) + 1  # 8  catch up
        return self.t                    # 9

Line 8 is the entire invention. max(t, stamp) + 1 is a machine saying: the moment this message arrived, my history includes everything the sender had seen — so my clock must read past both. The message doesn't just carry data anymore. It carries before-ness, and the receiver's counter absorbs it.

What the Number Promises

The guarantee, which the paper names the Clock Condition: if a happened before b, then a's stamp is strictly smaller than b's.

a → b ⟹ L(a) < L(b)

You can see why it holds without a proof course. Take any chain from a to b — the last lesson taught you every happened-before is a chain of two moves. Along one machine's own lane, the counter ticks up at every step. Across a message, the receiver takes max-plus-one, which lands strictly above the send. Every hop climbs; no hop ever descends; so the end of any chain reads higher than its start. The figure below walks one chain and you can watch the number climb every hop.

This one-way promise is already worth money. It means a Lamport stamp is a causality-safe sequence number: if you process events in stamp order, you will never process an effect before its cause. No wall clock ever gave you that; the previous lessons watched wall clocks stamp an arrival before its own send.

One chain across three machine lanes, its counter climbing at every hop: event a starts at 1 on machine A, a tick raises it to 2, a message hop lands on machine B as max-plus-one at 3, another tick makes 4, and a second message hop reaches machine C at 5 — event b. Each riser is labeled tick or max+1. The dark law band states the guarantee: a happened-before b implies L(a) < L(b). Foot: stamp order never plays an effect before its cause — a promise no wall clock ever made

What the Number Buries

Now the trap, and it deserves its own section because it is the single most common production misreading of logical clocks.

The Clock Condition is one-way. It says arrows force small-to-large. It does not say small-to-large implies an arrow. Turn it around and it simply fails: seeing L(a) < L(b) proves nothing about a and b. Maybe a chain runs from a to b. Maybe the two never heard of each other and the counters just happened to land that way — two machines ticking privately, one of them further along. The last lesson gave those pairs a name: concurrent. A Lamport clock takes every concurrent pair and quietly dresses it in ordered numbers anyway.

Call these impostor pairs: events whose stamps claim an order that causality never made. Every real history is full of them. The number compresses a partial order into a single integer line, and the compression is lossy — which pairs were genuinely independent is exactly the information that gets burned. The question the reframe lesson cared most about, what had each writer seen, cannot be answered by comparing two Lamport stamps. Ever.

So the discipline: a Lamport stamp may order your processing. It may never testify that one event caused, saw, or knew about another. When you catch yourself reading L(a) < L(b) as “a happened first” — and one day you will — remember the impostor below.

Two machine lanes, two events, no relationship: a sits quietly on machine A stamped 2; b sits busy on machine B stamped 9. The dashed line between them is broken by a circled question mark — no chain, either way. Below, on dark, the tempting claim is written out and struck through in red: 2 < 9, so a came first? Crossed out. Foot band: concurrent events wear ordered numbers anyway — the number orders, it never testifies

See It / Drive It: The Counter Lab

The lab below is the courtroom from the last lesson, rebuilt around the counter. Every event wears its number, computed live as you build the history.

Try this first: send a message from one machine to another, then click the receive. Its arithmetic pops open — max of what the machine knew and what the message brought, plus one. Do it again after letting the sender race ahead, and watch a receiver jump from 2 straight to 7: that jump is a machine swallowing another machine's history whole.

The strip along the bottom is the tie-broken total order: counter first, machine letter breaking ties. Rebuild the history however you like; the strip always re-sorts into one sequence, and here is the point: every machine, given the same events, derives exactly the same strip. Agreed order, no agreement protocol.

Then press find an impostor. Your job is to click a pair the counters appear to order but causality never did — ordered stamps, no chain. The lab checks both halves: the numbers must say before, and the graph must say concurrent. Finding one takes most people two tries, and the miss teaches as much as the hit — click a genuinely chained pair and the lab shows you the chain that convicts it.

The Counter Lab — the message diagram from the last lesson, with the counter as the star. Every event wears its Lamport number, computed live: local work ticks the machine's counter, a send carries the counter across, and clicking any receive shows its arithmetic — max of what the machine knew and what the message brought, plus one. The strip along the bottom is the tie-broken total order (counter first, machine letter second): rebuild the history any way you like and the strip re-sorts itself — an order every machine derives identically. Then take the hunt: press find an impostor and click two events whose numbers claim an order that causality never made — concurrent events wearing ordered stamps. Get it right and the lab confirms the one fact this lesson exists to install: the number orders events; it does not detect what really happened.

Where You've Already Shipped One

Here's the twist this course has been saving: you already trusted a Lamport clock with your data, two sections ago. The fencing token from Network Partitions & Split Brain — authority as a number that only goes up, token 5 bouncing off a gate that has seen 6 — is a logical clock. No wall time anywhere in it. A counter, carried on requests, compared at the resource. It worked precisely because it asked the number to do a logical clock's real job: impose an order everyone can check, without pretending to know what time it is.

The same species is everywhere once you know its face. Election epochs and leadership terms in coordination systems: counters that only rise, stamped on every message, so stale leaders' writes can be recognized and refused. Configuration generations. Schema versions. None of them are wall time; all of them are “a number that encodes came-after.”

And the tie-break trick from the lab — order by (counter, machine letter) — is original equipment: Lamport's paper uses exactly that to build a distributed mutual-exclusion queue, every machine deriving the same lock order with no coordinator. The deeper idea, that independent machines replaying the same stamped events reach identical decisions, is the seed of the replicated state machine — which is where this course is headed a few lessons from now. Hold that too.

One honest caveat before the takeaways: the total order is agreed, not true. Between genuinely concurrent events it's an arbitrary, if consistent, fiction. For processing order, arbitrary-but-agreed is exactly what you want. For deciding which of two independent writes “wins”, it has the same moral problem as last-write-wins, just with better clocks. Know which job you're hiring it for.

Key Takeaways

The whole clock is one integer and max-plus-one. Tick on every event, carry the counter on every message, catch up on every receive. Nine lines, counted.
The Clock Condition, one-way: a → b ⟹ L(a) < L(b). Counters climb every chain, so stamp order never processes an effect before its cause, a promise no wall clock made.
The converse fails, and that's the trap: L(a) < L(b) proves nothing. Concurrent events wear ordered numbers: impostor pairs. A Lamport stamp orders; it never testifies.
Tie-break to a total order, (counter, machine), and every machine derives the same sequence. Agreed, consistent, arbitrary between independents: perfect for processing, dishonest for deciding winners.
You've shipped this before. Fencing tokens, epochs, terms: numbers that only go up, carried on messages, checked at the resource. Logical clocks in work clothes.

The compression bought speed and burned one thing: the clock can no longer tell ordered from independent. But that burned information — what had each writer seen — is exactly what Version Conflicts needed to save Ana's hat, and one number per machine can't hold it. So stop compressing to one number. Keep one counter per machine, in a little vector, and concurrency stops hiding. That's next: Vector Clocks.