Vector Clocks

How to know whether two distributed updates conflict or whether one causes the other, without relying on synchronised wall clocks.

Problem

In a multi-master distributed system, two nodes may receive different updates on the same data while a network partition prevents them from communicating. On resolution, the system must decide: are these writes concurrent (conflict to resolve) or is one a causal consequence of the other (the latest wins)? A wall clock does not help — clocks drift (NTP has ~10ms accuracy in LAN, worse in WAN), and a causally later event can carry an earlier timestamp. We need a structure capturing causal order (happens-before, noted →), not temporal order.

Forces

• Memory footprint: a vector clock contains one entry per node, so N integers; explodes with the number of replicas.
• Garbage collection: removing entries of disappeared nodes is a problem in itself.
• Conflict detection, not resolution: VC says "there is conflict" but not "here is the correct value" — a business function is needed.
• No total order: a partial order is obtained; two concurrent events are incomparable.
• Comparison cost: hybrid logical clocks (HLC, Kulkarni 2014) offer a compromise between VC and physical clock.

Solution

Each node i maintains a vector VC[i] = [c1, c2, ..., cN]. On local event, VC[i][i] is incremented. On message send, VC[i] is attached. On reception, VC[i][k] = max(VC[i][k], VC[received][k]) for all k, then VC[i][i] is incremented. To compare two vector clocks VC(a) and VC(b): if VC(a)[k] ≤ VC(b)[k] for all k and at least one strict inequality, then a → b (a happens-before b). If neither a → b nor b → a, then a and b are concurrent — conflict to resolve. Dynamo (Amazon) stores several concurrent versions and lets the application merge them ("last-write-wins" or business logic).

Structure

Three nodes: A, B, C
Initial: VC_A = [0,0,0]   VC_B = [0,0,0]   VC_C = [0,0,0]

A writes "x=1"     → VC_A = [1,0,0]
A sends to B       → message carries VC = [1,0,0]
B receives, writes → VC_B = max([0,0,0], [1,0,0]) + own++ = [1,1,0]

Meanwhile, C writes "x=2" independently
                   → VC_C = [0,0,1]
C sends to B       → message carries VC = [0,0,1]

B compares its current VC_B = [1,1,0] with incoming [0,0,1]:
  Is [1,1,0] ≤ [0,0,1]? NO (1 > 0)
  Is [0,0,1] ≤ [1,1,0]? NO (1 > 0)
  → CONCURRENT! Conflict between "x=1 via A" and "x=2 via C"
  → Application must resolve (e.g., merge shopping cart, max value, ...)

EDI implementation

Vector clocks are not needed in the canonical EDI hub (where order is guaranteed by the central Kafka queue), but they are indispensable in two contexts: (1) multi-region active-active EDI hub on a CRDT store (Riak KV for example) where local writes synchronise in background — each write carries its VC, and conflict resolution is business-driven (the latest INVOIC received wins, or both are kept for audit); (2) edge computing for e-invoicing mandates — a partner emits an invoice from the edge while the central hub does too; VC lets you detect and trace these collisions. Amazon Dynamo (2007 paper) is the canonical example: it uses vector clocks for shopping carts where conflicts must be merged, not lost. For EDI, this kind of logic typically appears in the semantic dedup of credit notes that cross the original INVOIC mid-processing.

Anti-patterns

• Storing a VC per record with thousands of nodes — size explodes; use pruning or dotted version vectors.
• Relying on VC to resolve conflicts automatically — VC detects, the application resolves.
• Ignoring garbage collection — old nodes leave eternal entries in every vector.
• Mixing VC and wall timestamps — defeats the point of VC, which was precisely to avoid clock dependence.
• Assuming total order — VC provides a partial order; two concurrent events are incomparable by construction.

Related patterns

• Idempotency — combined with VC to distinguish real duplicates from concurrent ones.
• Event Sourcing — a distributed multi-region event store typically uses VC.
• Aggregator (EIP 268) — multi-message correlation can rely on VC.
• Consistent Hashing — combined with VC in Dynamo.

Sources

• Lamport L. — Time, Clocks, and the Ordering of Events in a Distributed System, CACM 1978. The foundational paper on logical clocks. lamport.azurewebsites.net
• Mattern F. — Virtual Time and Global States of Distributed Systems, 1989. Formalisation of vector clocks. vs.inf.ethz.ch
• Fidge C. — Timestamps in Message-Passing Systems That Preserve the Partial Ordering, 1988.
• DeCandia G. et al. — Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. Reference industrial application. allthingsdistributed.com
• Kleppmann M. — Designing Data-Intensive Applications, O'Reilly 2017, ch. 5 ("Replication").