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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.