Module 13 · Distributed fundamentals · Lesson 10 of 18
Vector clocks
One counter per participant, carried together, so that comparing two timestamps tells you exactly whether one event caused the other or they were concurrent. The rules.
The video walkthrough is part of Pro.
See what Pro includesWhy it matters
A user edits their profile on their phone while offline and on their laptop; both sync. Did one edit supersede the other, or did they happen independently? Lamport timestamps cannot say. Vector clocks can: they capture exactly what each replica had seen when it wrote, so the system can tell "this version descends from that one, keep the newer" apart from "these two are concurrent, surface both or merge". This is the mechanism under Dynamo, Riak and causal-consistency systems, and the standard follow-up after Lamport in interviews.
The idea
A vector clock is an array with one integer per process (or replica). Each process keeps its own vector.
- 1
Local event
Increment your own slot. - 2
Send
Increment your own slot and attach the whole vector to the message. - 3
Receive
Take the element-wise maximum of your vector and the received one, then increment your own slot.
Comparison: V(A) is less than V(B) if every element of V(A) is less than or equal to the corresponding element of V(B) and at least one is strictly less. Then A happened before B. If neither vector is less than the other, A and B are concurrent. Unlike Lamport clocks, this is an if-and-only-if: vector clocks capture causality exactly.
Version vectors in replicated stores
In a Dynamo-style key-value store, each stored value carries a version vector with one slot per replica (or per client) that has updated the key. A client reads the value and its vector, modifies it, and writes back with that vector as context. The replica compares: if the incoming vector descends from the stored one, it is a newer version and replaces it; if the stored one descends from the incoming, the write is stale and is ignored or rejected; if they are concurrent, the store keeps both as siblings and returns them on the next read, asking the client to reconcile (merge the shopping carts, pick the latest by application rule, or ask the user). That is how Amazon's cart never loses an item: concurrent adds become siblings that merge by union.
| Comparison result | Meaning | Store's action |
|---|---|---|
| Incoming > stored | Client saw the stored version and built on it | Replace |
| Incoming < stored | Client wrote based on an older version than what is stored | Reject or ignore as stale |
| Equal | Same version | No-op |
| Incomparable | Concurrent writes, neither saw the other | Keep siblings; reconcile on read |
Growth and dots
A vector has one slot per participant, so with many clients writing a key the vector grows. Dynamo pruned old entries past a size limit, accepting rare false concurrency. Dotted version vectors track the replica that coordinated each write (a "dot") and keep vectors sized by the number of replicas rather than the number of clients, which is what Riak uses. Causal-consistency systems that must track dependencies across many keys use compressed or coarse-grained vectors for the same reason.
Vector clocks versus the alternatives
Last-write-wins by timestamp is simplest and loses concurrent writes. Lamport timestamps give an order but hide concurrency. Vector clocks detect concurrency precisely at the cost of metadata size and a reconciliation step the application must implement. CRDTs, later in this module, remove the reconciliation step by making merges automatic for specific data types, often using vector-clock-like metadata underneath.