Vector Clocks

Imagine two servers on opposite sides of the planet, each editing the same shopping cart. One says the item was added at 10:00:00.000; the other says it was removed at 09:59:59.998. Did the removal really come first — or is one machine's clock just running a few milliseconds fast?

In a single computer, time is easy: one clock ticks, and every event gets a number. Across many machines there is no shared clock. Network delays jitter, quartz crystals drift, and synchronizing wall-clocks perfectly is physically impossible. So "what time did this happen?" is the wrong question.

The right question is causality: did event A influence event B, or did they happen independently? In 1978 Leslie Lamport reframed distributed time around this "happened-before" relation. Vector clocks — introduced independently by Colin Fidge and Friedrich Mattern in 1988 — capture it exactly, with nothing but counters and messages.

Three processes — A, B, C — run with no shared clock. Each keeps a small vector of counters, one slot per process. Do some local work or send a message, then click any two events to ask: did one cause the other, or are they concurrent?

<p class="hint">{{hint}}</p>
<div class="lanes" id="lanes"></div>
<div class="btns">
  <div class="proc-row">
    <span class="lbl">A</span>
    <button type="button" data-local="0">{{local_event}}</button>
    <button type="button" data-send="0:1">{{send_ab}}</button>
    <button type="button" data-send="0:2">{{send_ac}}</button>
  </div>
  <div class="proc-row">
    <span class="lbl">B</span>
    <button type="button" data-local="1">{{local_event}}</button>
    <button type="button" data-send="1:0">{{send_ba}}</button>
    <button type="button" data-send="1:2">{{send_bc}}</button>
  </div>
  <div class="proc-row">
    <span class="lbl">C</span>
    <button type="button" data-local="2">{{local_event}}</button>
    <button type="button" data-send="2:0">{{send_ca}}</button>
    <button type="button" data-send="2:1">{{send_cb}}</button>
  </div>
  <button type="button" id="reset" class="ghost">{{reset}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.lanes { display: flex; flex-direction: column; gap: .4rem; margin: .4rem 0 .8rem;
         border: 1px solid #cdd9e3; border-radius: 10px; padding: .5rem; min-height: 120px; background: #f6f9fb; }
.lane { display: flex; align-items: center; gap: .4rem; min-height: 40px; }
.lane-lbl { width: 22px; font-weight: 700; color: #1d3557; text-align: center; }
.evt { display: inline-flex; flex-direction: column; align-items: center; cursor: pointer;
       border: 1px solid #cdd9e3; background: #fff; border-radius: 8px; padding: 3px 7px;
       font: 600 12px ui-monospace, monospace; transition: all .1s; }
.evt:hover { border-color: #1d3557; }
.evt.send { background: #fff4e0; border-color: #e0a955; }
.evt.recv { background: #e4f3e8; border-color: #57b06f; }
.evt.sel { outline: 3px solid #1d3557; outline-offset: 1px; }
.evt .kind { font-size: 10px; color: #777; font-weight: 700; letter-spacing: .04em; }
.arrow { color: #e0a955; font-weight: 700; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; line-height: 1.4; }
.status.caused { color: #0a7d33; }
.status.conc { color: #b5630a; }
.btns { display: flex; flex-direction: column; gap: .4rem; }
.proc-row { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
.proc-row .lbl { width: 18px; font-weight: 700; color: #1d3557; }
button { font: 600 13px system-ui, sans-serif; padding: .35rem .7rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; align-self: flex-start; margin-top: .3rem; }

// Code not found

The rules are tiny. On any local or send event, a process bumps its own counter. When it receives a message it takes the element-wise maximum of its vector and the message's vector, then bumps its own counter again. To compare two stamps, check them slot by slot: if one is ≤ the other everywhere (and not equal), it happened-before it; if neither dominates, the events are concurrent. Notice how a $C$ event that never exchanged a message with $A$ always comes out concurrent — no amount of wall-clock guessing changes that.

What makes vector clocks more than a clever trick is that they capture causality exactly — this is a solved problem, proved correct by Fidge and Mattern in 1988.

• The model. With $n$ processes, each event gets a vector $V$ of $n$ counters. Local/send: V[i] += 1. Receive: V = max(V, message) element-wise, then V[i] += 1.
• The guarantee. For two events $U$ and $W$, $U$ happened-before $W$ if and only if U[k] ≤ W[k] for every $k$ and $U \ne W$. If neither vector dominates the other, the events are concurrent — provably causally independent.
• A partial order, not a line. Real concurrency has no single timeline. Vector clocks give the exact partial order of cause and effect, refusing to invent an order where none exists.
• The cost. Each stamp is $O(n)$ integers and every comparison is $O(n)$. That linear-in-the-number-of-processes overhead is the known price — and the reason large systems sometimes prune or compress the vectors.

Lamport's simpler scalar clocks (1978) are cheaper but lossy: they can tell you $U$ might have caused $W$, never that two events are genuinely concurrent. Vector clocks pay $O(n)$ to recover the full truth.

"Which update is newer, and do these two conflict?" is a question every distributed system must answer, and vector clocks (and their cousin, version vectors) are the standard tool:

• Eventually-consistent databases: Amazon's Dynamo and Riak attach version vectors to each value so replicas can detect when two writes are concurrent and surface a real conflict instead of silently losing data.
• Collaborative editing & CRDTs: live document editors track per-replica causality to merge keystrokes from many people without a central referee.
• Distributed debugging & tracing: when a bug spans dozens of services, vector clocks reconstruct what truly could have caused what, separating real dependencies from coincidence.
• Version control: the "did these branches diverge?" logic in Git-like systems is the same happened-before test, dressed up as commit ancestry.

Understand vector clocks and you understand the difference between order and causality — the same distinction that haunts everything from databases to the limits of computation.

Vector clocks make peace with a hard truth: across many machines there is no single "now." Instead of faking a global timeline, they track who-knew-what with a vector of counters — and from those counters they read off, exactly, which events caused which and which are forever concurrent.

It is a rare thing in computing: a problem that is genuinely solved, cheaply, and beautifully. The next time two servers disagree about what happened first, remember that the honest answer is often "neither" — and that a handful of integers can prove it.