Vector Clocks & CRDTs

In a distributed system without a single source of truth, two replicas can accept writes to the same key at the same time, neither aware of the other. When they finally sync, you face the question that haunts every eventually-consistent store: which write wins, and how do you even know there was a conflict? Wall-clock timestamps lie (clocks drift; “last write wins” silently discards data). This page is about two ideas that confront the problem head-on: vector clocks, which detect concurrency, and CRDTs, which make conflicts resolve themselves.

Why timestamps can’t tell you what happened

The deep issue is that “happened before” is about causality, not calendar time. If write A could have influenced write B (B’s author had seen A), then A is causally before B and B is the obvious winner. But if A and B were made independently, in ignorance of each other, then there is no “right” winner — they are concurrent, and you have a genuine conflict that no timestamp can adjudicate honestly. This is the territory mapped out in Time, Clocks & Ordering: physical clocks measure the wrong thing. We need a clock that measures causality instead.

Vector clocks: a clock that counts causality

A vector clock gives every replica a counter, and every value carries a vector of all replicas’ counters as last seen by the writer. The rules are tiny:

• Each node increments its own entry on every local write.
• When a node receives/merges a value, it takes the element-wise maximum of the two vectors, then increments its own entry.

To compare two vectors V and W:

V "happened before" W   if every V[i] <= W[i]  and at least one V[i] < W[i]
W "happened before" V   (the mirror of the above)
V and W are CONCURRENT   if neither dominates — each has some entry the other lacks

Worked example with three replicas A, B, C:

A writes x:  [A:1, B:0, C:0]
B reads that, then writes:  [A:1, B:1, C:0]   ← B saw A, so B's write is causally AFTER A
                                                ([1,0,0] <= [1,1,0]) — B wins cleanly.

Meanwhile C, never having seen A, writes:  [A:0, B:0, C:1]
Compare [A:1,B:1,C:0] vs [A:0,B:0,C:1]:
   neither <= the other  →  CONCURRENT  →  real conflict, surface BOTH versions.

That last line is the magic and the catch. A vector clock won’t resolve the conflict — it will honestly tell you one exists so you don’t silently lose data. Systems like Dynamo and Riak return both sibling versions to the application and say “you decide” (merge a shopping cart by union, ask the user, pick by a domain rule).

The cost of honesty

Vector clocks buy you correct conflict detection — no more silent lost updates from last-write-wins. The cost: the vector grows with the number of writers, the application must handle sibling versions, and pruning old entries safely is fiddly. You’ve traded a comfortable lie for an uncomfortable truth you now have to act on.

CRDTs: data types that merge themselves

Surfacing siblings to the application is honest but exhausting. What if the data type itself were designed so that any two replicas, merged in any order, always converge to the same answer — no conflicts to resolve, ever? That is a Conflict-free Replicated Data Type (CRDT).

The trick is mathematical. If the merge operation is commutative, associative, and idempotent (a join-semilattice, formally), then it doesn’t matter what order updates arrive, whether they arrive twice, or which replica merges first — everyone ends up identical. The network can reorder, duplicate, and delay messages all it wants; convergence is guaranteed by algebra, not by careful coordination.

Some workhorse CRDTs:

G-Counter   grow-only counter. Each node keeps its own count; value = SUM,
            merge = element-wise MAX. Increments never conflict.

PN-Counter  two G-Counters (one for + , one for -); value = P_sum - N_sum.
            Now you can decrement too.

OR-Set      observed-remove set. Each add tags the element with a unique id;
            remove deletes only the ids it has SEEN. Merge = union of adds
            minus union of seen-removes. Re-adding after a concurrent remove
            survives — "add wins."

LWW-Register single value with a timestamp; merge keeps the higher timestamp.
            (Simple, but reintroduces last-write-wins data loss.)

A G-Counter shows the whole idea in miniature:

Node A increments 3x → {A:3, B:0}
Node B increments 2x → {A:0, B:2}
merge (element-wise max) → {A:3, B:2}  → value = 5
Merge it again, or in the other order: still {A:3, B:2} → 5. Convergent.

Collaborative editors (the text-CRDT behind real-time docs), distributed counters (likes, view counts), shopping carts, and presence systems all lean on CRDTs to let many replicas accept writes offline and reconcile automatically.

CRDTs vs vector clocks

They’re not rivals — they’re different layers. A vector clock detects concurrency and hands you two siblings. A CRDT defines a merge so the siblings collapse automatically. Many CRDTs use vector-clock-like causal metadata internally; the CRDT is what you build on top of detection so the application never has to choose a winner by hand.

The price of automatic merging

CRDTs make eventual consistency usable — replicas accept writes independently, tolerate partitions, and converge with no coordination — which is enormous for availability and offline-first apps. But the price is steep and specific. You must model your data as one of these constrained algebraic types; not every operation fits (“set this field to exactly X, overriding all concurrent writers” is fundamentally non-mergeable, so you fall back to LWW and accept loss). The metadata can balloon (tombstones in an OR-Set must linger so a delete isn’t forgotten). And the merge semantics may not match human intent — “add wins” is a policy, and sometimes the user wanted “remove wins.” You buy coordination-free convergence; you pay in expressiveness and bookkeeping.

The thread

How do mutually-out-of-sync replicas agree on one value? You can’t use wall-clock time, because the real question is causal, not chronological. Vector clocks give you an honest causal comparison — ordered or concurrent — so you never silently lose a write. CRDTs go further: by constraining the data to types whose merges are commutative, associative, and idempotent, they let replicas converge automatically, turning “eventual consistency” from a polite way of saying “we might drop your data” into a real, well-defined guarantee.

Check your understanding

1. Why can’t a wall-clock timestamp correctly decide a winner between two writes? What property is it measuring instead of the one that matters?
2. Given two vectors, state the exact test for “A happened before B” versus “A and B are concurrent.”
3. A vector clock tells you a conflict exists but not how to resolve it. Whose job is resolution, and name two real strategies.
4. What three algebraic properties must a CRDT’s merge satisfy, and why does each one matter given an unreliable network?
5. Give one real operation that cannot be modeled as a clean CRDT, and explain what you give up if you force it.