yield point
Distributed Systemsdeepupdated 2026-08-22

Vector clocks and causal order

Timestamps cannot tell you whether two events conflicted or merely happened at different times, and picking the larger one silently deletes half of every genuine conflict.

Two replicas both hold a value. Each receives an update. When they reconcile, which update wins?

The tempting answer is “whichever has the later timestamp”, and it is wrong in a way that loses data quietly. Two clocks on two machines are not comparable - and even if they were, a later timestamp does not mean the writer knew about the earlier write.

Partition the nodes and watch the concurrent-pair count climb. Those are exactly the updates a last-write-wins policy would throw away without telling you.

N0[0,0,0]N1[0,0,0]N2[0,0,0]
Events
0
In flight
0
Concurrent pairs
0
tick 0 / 900
Break it
Do
Safety properties
  • ✓
    A received event always happens-after its cause

    held on every tick so far

What a timestamp cannot say

Lamport’s insight was that what matters in a distributed system is not when things happened but what could have influenced what.[1]paperTime, Clocks, and the Ordering of Events in a Distributed SystemLamport, L., Communications of the ACM 21(7), 1978 Event a happens-before event b if a could have causally affected b: same node and earlier, or connected by a message.

Two events with no such path are concurrent. Not “at the same time” - that is not even well defined - but genuinely unordered. Neither could have known about the other.

A wall-clock timestamp collapses that distinction. It gives you a total order over events that are only partially ordered, and the extra ordering it invents is fiction.

How the vector works

Each node keeps a vector with one counter per node.[2]paperTimestamps in Message-Passing Systems That Preserve the Partial OrderingFidge, C. J., ACSC '88, 1988

  • Increment your own entry on every local event.
  • Attach your whole vector to every message you send.
  • On receipt, take the element-wise maximum of your vector and theirs, then increment your own entry.

Then, comparing two clocks:

a happens-before b   ⟺   ∀i: a[i] ≤ b[i]   and   ∃i: a[i] < b[i]
a concurrent with b  ⟺   neither happens-before the other

The vectors are visible under each node in the widget. Watch one node’s entry rise in another node’s vector as messages arrive - that is causal knowledge propagating.

Concurrency is the useful output

Press Partition. Both sides carry on accepting writes, neither learns about the other, and the concurrent-pair count climbs.

Every one of those pairs is a case where last-write-wins would pick one and destroy the other. With vector clocks you at least know. Dynamo’s design returns all concurrent versions to the client - siblings - and makes the application decide, because only the application knows whether two updates to a shopping cart should merge or replace.[3]paperDynamo: Amazon's Highly Available Key-value StoreDeCandia, G. et al., SOSP '07, 2007

Why they are hard in practice

The metadata grows with the number of writers. A vector clock with one entry per client becomes larger than the value it describes, which is why Dynamo used node identifiers rather than client identifiers and truncated old entries - a pragmatic choice that can, in rare cases, lose the very causality the mechanism exists to preserve.[3]paperDynamo: Amazon's Highly Available Key-value StoreDeCandia, G. et al., SOSP '07, 2007

Riak’s engineers wrote candidly about the practical difficulties, and the honest summary is that vector clocks are simple to define and awkward to operate.[4]articleWhy Vector Clocks Are HardBrown, J., 2010

This is much of why CRDTs became popular: rather than detecting conflicts and asking the application to resolve them, design the data type so concurrent updates merge deterministically and there is nothing to resolve. That trades expressiveness for the removal of an entire class of decisions.

The cheaper cousin

A Lamport clock is a single counter: increment on each event, and on receipt take max(local, received) + 1.[1]paperTime, Clocks, and the Ordering of Events in a Distributed SystemLamport, L., Communications of the ACM 21(7), 1978 It gives a total order consistent with causality, which is enough when you only need an agreed order - but it cannot tell you whether two events were concurrent, because it has thrown away the per-node detail. If a < b, a may have happened before b, or they may be unrelated. Vector clocks pay n counters to answer exactly that question.

The dial

You gainExact detection of which updates are causally related and which genuinely conflict
You payMetadata that grows with the number of writers, and conflicts you now have to resolve yourself

The line - when someone asks

A vector clock gives each node a counter per node: you increment your own on every event and take the element-wise maximum whenever you receive a message. One clock happens-before another if every entry is less than or equal and at least one is strictly less; if neither dominates, the events are concurrent. That distinction is what wall-clock timestamps cannot express, and it is the difference between resolving a conflict and silently discarding one side of it.

Recall

Loading…

Where are you with this?

Saved on this device. Sign in to keep it across devices.

Sources

Primary

Secondary