Introduction

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.

Pass the 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">Three processes (A, B, C) run with <b>no shared clock</b>. Each keeps a
vector counting events it knows about on every process. Click <b>Local event</b> to do
work, or <b>Send</b> to ship a message that carries the sender's vector. Pick any two
events to see whether one <i>caused</i> the other or they are truly <b>concurrent</b>.</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 A→B</button>
    <button type="button" data-send="0:2">Send A→C</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 B→A</button>
    <button type="button" data-send="1:2">Send B→C</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 C→A</button>
    <button type="button" data-send="2:1">Send C→B</button>
  </div>
  <button type="button" id="reset" class="ghost">Reset</button>
</div>
<div class="status" id="status">Click events. Then click two of them to compare.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Vector clocks (Fidge & Mattern, 1988) order events across processes that share
// NO global clock. Each process i keeps a vector V of length n. Rules:
//  - local/send event on i:  V[i] += 1
//  - receive of message msg:  V = elementwise max(V, msg), then V[i] += 1
// Causality test for two stamped events U, W:
//  - U "happened-before" W  iff  U[k] <= W[k] for all k  AND  U != W
//  - if neither happens-before the other, the events are CONCURRENT.
const N = 3, NAMES = ['A','B','C'];
let clocks, events, pending, sel;
function init(){
  clocks = [ [0,0,0], [0,0,0], [0,0,0] ];   // current vector per process
  events = [];                               // {id, proc, kind, vc, link}
  pending = [];                              // in-flight messages {to, vc, fromEvt}
  sel = [];
  render();
  setStatus('Click events. Then click two of them to compare.','');
}
function tick(p){ clocks[p][p]++; }
function snapshot(p){ return clocks[p].slice(); }
function localEvent(p){
  tick(p);
  events.push({id:events.length, proc:p, kind:'local', vc:snapshot(p)});
  // deliver any message waiting for p (FIFO) as a receive on the SAME click chain? No:
  // keep send/receive explicit so causality is visible.
  render();
}
function send(from,to){
  tick(from);
  const e={id:events.length, proc:from, kind:'send', vc:snapshot(from)};
  events.push(e);
  pending.push({to, vc:snapshot(from), fromEvt:e.id});
  render();
  setStatus(fmt('Message in flight to %v%. It is delivered automatically.', { v: NAMES[to] }),'');
  // auto-deliver shortly after, so the receive event appears
  setTimeout(()=>deliver(to),350);
}
function deliver(to){
  const idx = pending.findIndex(m=>m.to===to);
  if(idx<0) return;
  const m = pending.splice(idx,1)[0];
  // merge: elementwise max, then bump own component
  for(let k=0;k<N;k++) clocks[to][k]=Math.max(clocks[to][k], m.vc[k]);
  clocks[to][to]++;
  events.push({id:events.length, proc:to, kind:'recv', vc:snapshot(to), link:m.fromEvt});
  render();
}
function vcStr(v){ return '['+v.join(',')+']'; }
// returns 'before' if a<b, 'after' if b<a, 'concurrent' otherwise
function compare(a,b){
  let le=true, ge=true, eq=true;
  for(let k=0;k<N;k++){ if(a[k]>b[k]) le=false; if(a[k]<b[k]) ge=false; if(a[k]!==b[k]) eq=false; }
  if(eq) return 'equal';
  if(le) return 'before';
  if(ge) return 'after';
  return 'concurrent';
}
function render(){
  const root=document.getElementById('lanes'); root.innerHTML='';
  for(let p=0;p<N;p++){
    const lane=document.createElement('div'); lane.className='lane';
    const lbl=document.createElement('span'); lbl.className='lane-lbl'; lbl.textContent=NAMES[p];
    lane.appendChild(lbl);
    events.filter(e=>e.proc===p).forEach(e=>{
      if(e.kind==='recv'){ const ar=document.createElement('span'); ar.className='arrow'; ar.textContent='→'; lane.appendChild(ar); }
      const el=document.createElement('div');
      el.className='evt '+(e.kind==='send'?'send':e.kind==='recv'?'recv':'')+(sel.includes(e.id)?' sel':'');
      el.innerHTML='<span class="kind">'+e.kind+'</span>'+vcStr(e.vc);
      el.addEventListener('click',()=>pick(e.id));
      lane.appendChild(el);
    });
    root.appendChild(lane);
  }
}
function pick(id){
  if(sel.includes(id)) sel=sel.filter(x=>x!==id);
  else { sel.push(id); if(sel.length>2) sel.shift(); }
  render();
  if(sel.length===2){
    const a=events[sel[0]], b=events[sel[1]];
    const rel=compare(a.vc,b.vc);
    const an=NAMES[a.proc]+' '+vcStr(a.vc), bn=NAMES[b.proc]+' '+vcStr(b.vc);
    if(rel==='before') setStatus(fmt('Causal: %an%  → happened-before →  %bn%', { an: an, bn: bn }),'caused');
    else if(rel==='after') setStatus(fmt('Causal: %bn%  → happened-before →  %an%', { bn: bn, an: an }),'caused');
    else if(rel==='equal') setStatus('Same event.','');
    else setStatus(fmt('CONCURRENT: %an% and %bn% are causally independent — neither vector ≤ the other.', { an: an, bn: bn }),'conc');
  } else setStatus('Pick one more event to compare.','');
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
document.querySelectorAll('[data-local]').forEach(b=>b.addEventListener('click',()=>localEvent(+b.dataset.local)));
document.querySelectorAll('[data-send]').forEach(b=>b.addEventListener('click',()=>{ const [f,t]=b.dataset.send.split(':').map(Number); send(f,t); }));
document.getElementById('reset').addEventListener('click',init);
init();
Result
Console

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 CC event that never exchanged a message with AA always comes out concurrent — no amount of wall-clock guessing changes that.

The Real Mechanism

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 nn processes, each event gets a vector VV of nn counters. Local/send: V[i] += 1. Receive: V = max(V, message) element-wise, then V[i] += 1.
  • The guarantee. For two events UU and WW, UU happened-before WW if and only if U[k] ≤ W[k] for every kk and U≠WU \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)O(n) integers and every comparison is O(n)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 UU might have caused WW, never that two events are genuinely concurrent. Vector clocks pay O(n)O(n) to recover the full truth.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/vector-clocks/Content licensed under CC BY-NC 4.0.