Vector Clocks

Two lessons have written a promissory note with today's date on it. Version Conflicts watched last-write-wins destroy Ana's hat and said the cure exists: a structure that tracks what each writer had seen, rather than what its clock said — and it's called a vector clock. And the last lesson ended at the exact same door from the other side: the Lamport clock compresses history into one number and burns precisely that information. Keep one counter per machine, it said, in a little vector — and concurrency stops hiding.

So this lesson owes you three things: the algorithm (barely bigger than the nine lines you already know), the theorem that makes it special (the one-way promise becomes two-way), and the payoff you were promised two sections ago — Ana's hat, saved, on screen, by arithmetic.

Take the Lamport clock and refuse to compress. Three machines, so every stamp is now a little table of three counters — one slot per machine. Machine B's rules, with its own slot in the middle:

1. Tick your own slot before every local event. Only yours. B never invents news about A or C.
2. Send the whole vector with every message.
3. On receive, take the elementwise max, then tick your own slot. Slot by slot, keep whichever count is larger — mine or the message's — because each slot is a claim about one machine's history, and the bigger number simply knows more of it.

Now read a vector as what it literally is. An event on machine B stamped [3, 1, 4] says: by the time I happened, B had absorbed 3 events of A's story, this was B's own 1st, and 4 of C's had reached me. That's not a timestamp. That's a memory — a receipt of everything this event could possibly have known. The phrase from Version Conflicts was exact: the vector tracks what each writer had seen.

Comparing two memories is one rule: V(a) < V(b) when every slot of a is ≤ the matching slot of b, and at least one is strictly smaller. In words: b's memory contains a's memory, and then some. When neither contains the other — a is ahead in one slot, b ahead in another — the vectors are incomparable.

And now the theorem that earns this lesson its place. The Lamport clock gave a one-way promise; the vector gives both directions:

a → b ⟺ V(a) < V(b)

Read the arrow both ways. A chain from a to b forces a's vector strictly inside b's — same argument as before, every hop grows the memory. But now the converse holds too: if a's vector sits strictly inside b's, then b had absorbed everything a knew, and that can only happen through a chain of messages. Which flips the whole game, because the leftover case finally means something: incomparable vectors are a proof of concurrency. Not a shrug — a certificate. One slot says a ran ahead of what b had seen; another says the reverse; therefore neither could have known about the other. The impostor pairs that hid inside Lamport numbers stand fully exposed.

The last lesson's law was the number orders; it never testifies. The vector testifies. That is the entire upgrade, and it costs exactly one counter per participant.

Replay the crime scene from Version Conflicts, instruments upgraded. Ana's cart lives on replicas. Her hat write lands on one node; moments later, on a node that had not seen the hat, the lamp write lands. In the original telling, the lamp's node had a clock five seconds fast, last-write-wins compared two wall-clock stamps, and the hat — written earlier, stamped later — was destroyed. A node with a fast clock wins every race it ever enters.

Now the same two writes carry vectors. The hat write's vector is ahead in its own node's slot; the lamp write's vector is ahead in its node's slot; neither contains the other. Incomparable. The store doesn't guess — it knows these are causal strangers, and it does the only honest thing: keeps both, as siblings, and hands the pair to the next read. The cart shows hat and lamp; the merge happens where the data model can decide. And the test for how to merge is one you already own — Version Conflicts drilled it: is this value a snapshot, or an accumulation? A cart is an accumulation; the union has no losers.

Notice what did not get fixed: the broken clock. That node is still five seconds fast. It no longer matters, because nobody consulted it. The murder weapon wasn't the clock — it was the question “whose stamp is bigger?”, asked of two writers who had never met.

The counter lab, upgraded: every event now wears its full vector, computed live as you build.

Try this first: send a message and click its receive. The arithmetic panel shows the elementwise max absorbing the sender's history slot by slot, then the receiver's own tick. That one operation is the whole machine: memories merging.

Then pick any two events. The comparison panel lines the vectors up and judges every slot — and unlike last lesson's judge, this one never shrugs. Either one memory contains the other (the chain lights up to show why), or one slot points each way and the verdict stamps CONCURRENT — proven. Load save the hat to watch the crime from Version Conflicts die on arrival: the hat and lamp writes come out incomparable, the store keeps both, and a small ghost shows the write that last-write-wins would have silently destroyed.

Then prove you can weaponize it — press make a conflict. Build any history you like and pick a pair whose vectors certify that neither writer had seen the other. If you pick a chained pair instead, the lab lights the chain that convicts you, and you'll know exactly why.

Honesty has a price list, and vectors pay in three currencies.

Space. One counter per participant, on every stamp, on every message. Three replicas is nothing; a slot for every client that ever wrote is not. Amazon's Dynamo — the system that made this technique famous for shopping carts — capped the vector and, past a threshold of about ten entries, truncated the oldest pair. That can theoretically break ancestry detection; the paper shrugs, in writing, that the problem “has not surfaced in production.” Real engineering, visible seams.

Vocabulary. What object stores actually ship is usually the vector's working-class cousin, the version vector: one slot per replica, tracking versions of one object, rather than one slot per actor for every event in the universe. Same math, same comparison rule, narrower and cheaper job. If a database's docs say “vector clock”, they almost always mean this.

Aftercare. The vector detects; it does not resolve. Siblings pile up on hot keys, and somebody — your code, at read time — has to merge or choose. That cost is exactly why Version Conflicts found last-write-wins as the industry default: LWW won on price, not on correctness. The decision rule survives contact with the bill: for snapshots, LWW is correct and vectors are overkill; for accumulations — carts, counters, permissions — the vector's honesty is the difference between merging two truths and silently deleting one.

Later in this course, when replicas collaborate on shared state, you'll meet data types engineered so the merge is automatic and conflict-free. The vector is how systems see concurrency; what to do with it stays a design decision.

• Refuse to compress: one counter per machine. Tick your own slot; send the whole vector; on receive, elementwise max, then tick. A stamp becomes a memory of what this event had seen.
• The theorem goes both ways now: a → b ⟺ V(a) < V(b). Containment of memories is exactly causality. The Lamport clock ordered; the vector testifies.
• Incomparable = concurrent, proven. One slot ahead each way is a certificate that neither writer had seen the other — the impostor pairs stand exposed.
• Detection changes the verdict: keep both. Ana's hat survives as a sibling, the merge moves to read time, and the snapshot-vs-accumulation test decides how. The broken clock stays broken; nobody asks it anything.
• The bill is real. O(n) stamps, truncation (Dynamo, ~10 entries, “has not surfaced in production”), version vectors as the shipped cousin, and sibling aftercare — which is why LWW still wins on price for snapshots.

You now hold the whole logical-time toolkit: happened-before, the cheap number that orders, the vector that testifies. What's left is the part interviews and incidents actually serve up: real systems that need IDs that sort, events that carry two times (when it happened versus when you learned of it), and the discipline of choosing the right ordering tool per job. That's next: Ordering in Practice.