Beyond a single counter
Lamport clocks order events but cannot tell whether two events are concurrent. Vector clocks fix this by storing a vector of counters, one entry per process, instead of a single number.
How they update
Each process holds a vector indexed by every process.
- On a local event, a process increments its own entry.
- On sending, it includes the whole vector.
- On receiving, it takes the element wise maximum of its vector and the received one, then increments its own entry.
Comparing vectors
Compare two vectors entry by entry.
- If every entry of A is less than or equal to B and at least one is strictly less, then A happened before B.
- If neither dominates the other, the events are concurrent.
This direct test for concurrency is the key advantage. The cost is that the vector grows with the number of processes, which can be large in big clusters.
Key idea
Vector clocks store one counter per process, so comparing vectors reveals both ordering and true concurrency, at the cost of size that grows with the number of processes.