Notesdistributed🌱 seedling
Vector Clock
Also: Vector Clocks · Vector Timestamp
Each process keeps a vector of counters, one per process, merged element-wise on receipt. Comparing two vectors entry by entry tells you exactly whether one event happened before the other or they were concurrent.
Why it exists
Lamport Clocks order events but can't detect concurrency, and detecting concurrent writes is the whole job of conflict handling.
How it works
- Before each event, a process increments its own entry.
- Messages carry the whole vector; the receiver takes the element-wise max, then increments its own entry.
- Compare: V(a) ≤ V(b) in every entry (and differ somewhere) ⇔ a → b. If each is larger somewhere, a ∥ b.
- Each entry records how much of one process's history the event has seen.
Trade-offs
| Gains | Costs |
|---|---|
| exact causality and concurrency detection | size grows with the number of processes |
| no synchronized clocks | per-client entries explode; pruning risks false conflicts |
In practice
- Dynamo attached vector clocks to object versions to detect conflicting writes, truncating the oldest entries past a size threshold.
- Databases usually track one entry per replica instead of per client: a Version Vector. Riak moved to dotted version vectors to avoid sibling explosion.
Pitfalls
- Confusing vector clocks (per process, ordering events) with version vectors (per replica, versioning one key's values). Similar maths, different job.
- Letting entries accumulate for short-lived clients.
Connections
- Contrasts with
- Lamport Clock
- In real systems
- Dynamo
Recall
These cards are also in your review deck, scheduled with spaced repetition.