Version vector
Version vector is a mechanism that generates a pre-order in a distributed system. It enables causality tracking among data replicas and is a basic mechanism for optimistic replication. The state in a version vector is identical to the state in a vector clock but with diferent update rules:
- Initially all vector counters are zero.
- Each time a replica experiences an update event, it increments its own counter in the vector by one.
- Each time two replicas synchronize, both resulting vectors are identical and will depict the pairwise maximum between the two vectors across all counters.
Version vectors or variants are used in many distributed file systems to track updates, and are the main data structure behind optimistic replication [1]. For example Internet explorer stores version vectors in the Windows registry.
References
- ^ David Ratner, Peter Reiher, and Gerald Popek. Dynamic version vector maintenance. Technical Report CSD-970022, Department of Computer Science, University of California, Los Angeles, 1997