← Back to blogs

WTH is Vector Clocks & Conflict Resolution?

A quorum tells you which replicas to contact. Vector clocks tell you whether two updates happened one-after- the-other or truly at the same time — and that distinction is exactly where "replica divergence" becomes a "conflict" you must resolve. Without it, you cannot tell a lost update from a concurrent one.

1. The Ordering Problem

In a single process, "before" is easy: events have a total order, and we know which one happened first. In a distributed system, an event on node A and an event on node B have no shared clock, so "before" is only defined when there is a chain of observation — a message, a shared read, or a broadcast. This relation is called happens-before:

• On the same process, event a happens-before b if a precedes b in local order.
• If process P sends a message and process Q receives it, the send happens-before the receive.
• Happens-before is transitive: if a → b and b → c, then a → c.

Two events are concurrent when neither happens-before the other. Concurrency is the interesting case: neither event "saw" the other, so no clock from a single point of view can order them.

2. Physical Clocks, Lamport Clocks, and Their Limits

Wall-clock timestamps look like an answer. Two events get NTP-synced timestamps and you compare them. The problem: NTP skew can be tens of milliseconds, and network transmission adds latency that no local timestamp captures. Physical clocks cannot prove causality, and LWW built on them silently discards the "losing" write.

Lamport clocks solve part of this. Each process keeps an integer counter:

• Before each event, increment the counter.
• Attach the counter to every message.
• On receive, set counter = max(counter, received) + 1.

A Lamport clock guarantees that if a → b then C(a) < C(b). But the converse is false: C(a) < C(b) does not mean a → b. Two concurrent events can get ordered timestamps that imply a causality that never existed. A Lamport clock gives you a total order consistent with causality — it cannot detect concurrency.

3. Vector Clocks: Structure and Rules

A vector clock gives each process a vector of counters — one entry per process in the system. For processes P1, P2, P3, the clock on any node is (c1, c2, c3):

1. Local event: increment your own entry: (1,0,0) → (2,0,0).
2. Send: attach your full vector to the message.
3. Receive: take the element-wise max of your vector and the received one, then increment your own entry.

P1: (1,0,0) → local event → (2,0,0) → send "(2,0,0)" to P2
P2 receives (2,0,0), max with own (0,1,0) → (2,1,0), +1 own → (2,2,0)

4. Comparing Vectors

Given two vectors V and U, compare element-wise:

• V ≤ U (every component ≤): V happened-before or equals U.
• V < U (≤ and at least one strictly <): V happens-before U.
• Neither ≤ nor ≥: concurrent — no causal path between them.

(1,0,0) < (1,2,0)  → happens-before
(1,2,0) vs (0,0,1) → incomparable → concurrent
(1,2,0) vs (1,2,0) → equal (same event, or identical context)

This is the entire point: vector clocks turn "which one is newer?" from a guess into a well-defined three-way comparison. Incomparable means concurrent means conflict.

5. Concurrent Updates Are Conflicts

Now apply this to replicated data. Two replicas of the same key receive updates from different clients at the same time. Each update carries a vector clock. When the replicas reconcile:

• Happens-before: one update descends from the other — keep the newer one, done.
• Concurrent: neither descends from the other — both are valid, and silently keeping one discards a real user change. That is a conflict, and it must be surfaced or resolved by policy.

A vector clock does not resolve the conflict; it detects it precisely and definitively. Detection is the hard part, and everything else is policy.

6. Resolving Conflicts: LWW, Version Vectors, CRDTs, App Merges

• LWW: pick the highest timestamp. Simple, but treats concurrency as if it were ordering — and under clock skew it can discard the update that actually mattered.
• Vector clocks / version vectors: keep both versions as siblings and require the application to merge them. Dynamo, Riak, CouchDB do this. The cost: reads may return multiple values, and sibling lists can grow without pruning.
• CRDTs: make the merge commutative, associative, and idempotent so any order of merging yields the same result — no conflict to resolve, by construction.
• Application merge: explicit domain logic ("add the two carts", "union the tag sets") applied to siblings before returning.

The right choice depends on whether your operations commute. CRDTs commute by design; arbitrary updates usually do not, which is why sibling resolution exists.

7. CRDT Examples

G-Counter (grow-only): each node owns an entry; merge = max per entry.
  "like counts" where only increments happen → no conflict ever.

PN-Counter (increments + decrements): a grow-only counter for incs and one for decs.

LWW-Register: value + timestamp; merge keeps the later timestamp — a CRDT that
  "resolves" the way LWW would, but associatively.

OR-Set (observed-remove set): tombstones removed elements so re-adds are not
  swallowed by a stale remove.

CRDTs trade generality for convergence: they only work for operations that commute. If you need arbitrary transactions or "the latest wins," a CRDT is the wrong tool.

8. Vector Clocks in Production

• Dynamo / Riak: each value stores a vector clock; concurrent writes become siblings returned to the client with the clock for merging. The 2007 Dynamo paper is the canonical reference.
• Cassandra: uses LWW by default; version vectors (a bounded variant) are available for the same conflict-detection purpose. The distinction matters: version vectors fix the size per key but keep the causality semantics.
• Distributed file systems / multi-master sync: version vectors detect concurrent edits to the same file and hand the merge to the client (Git's merge machinery is the same idea with commit graphs).

The detail that bites in production is pruning: vector clocks grow with the number of nodes, so systems either bound them (version vectors) or compact them over time. Compaction trades precision: a pruned clock may classify two ordered updates as concurrent.

9. Memory and Practical Tradeoffs

• Size: a full vector clock is O(nodes). At thousands of nodes, storing one per value is not free — version vectors and dot-based clocks bound the cost per key.
• Node churn: adding a node changes the vector length. Systems handle this with per-key clocks instead of cluster-wide vectors.
• Stale clocks: an old node rejoining with an ancient clock can misorder merges; fencing or clock compaction is required.
• Conflict visibility: sibling lists that never converge force the application to resolve forever. CRDTs avoid this; vector clocks do not.

10. Event-Lattice / Causality Diagram

Below is a small causality diagram. Each circle is an event labeled with its id and vector clock; an arrow means the source happens-before the target. Notice the two events marked dashed: C and E have incomparable vectors, so they are concurrent — the exact moment a divergence becomes a conflict.

Reading the diagram: A → B → C → D, and E → F → G on P3. But E has no causal path to C — their vectors are incomparable, so E and C are concurrent. Two replicas holding those updates have a genuine conflict, not a resolvable ordering.

11. Key Takeaways

• Physical clocks cannot prove causality; Lamport clocks order but cannot detect concurrency.
• Vector clocks detect concurrency precisely: incomparable vectors mean concurrent means conflict.
• Detection is not resolution — siblings need a policy (LWW, CRDT, or application merge).
• Version vectors bound the cost per key; pruning trades a little precision for a lot of memory.
• Choose CRDTs when operations commute, vector-clock siblings when you need to surface conflicts, and LWW only when losing a concurrent update is acceptable.

Vector clocks answer "was this update concurrent?" — they do not answer "can we make several resources commit or abort together?" Atomicity across nodes is a different problem, and it is the job of two-phase commit, where a coordinator turns "in-doubt" into the DBAs' worst nightmare.