Version vector

A version vector is a mechanism for tracking changes to data in a distributed system, where multiple agents might update the data at different times. A version vector works by generating a preorder to keep track of update events that precede, and may therefore influence later updates. 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 different 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.

Pairs of replicas, $a$, $b$, can be compared by inspecting their version vectors and determined to be either: identical ($a=b$), concurrent ($a\parallel b$), or ordered ($a<b$ or $b<a$).

Version vectorsor variants are used in many distributed file systems to track updates, see Coda (file system) and Ficus, and are the main data structure behind optimistic replication . For example Internet explorer stores version vectors in the Windows registry.

Other Mechanisms

• Hash Histories avoid the use of counters by keeping a set of hashes of each updated version and comparing those sets by set inclusion. However this mechanism can only give probabilistic guaranties.
• Concise Version Vectors allow significant space savings when handling multiple replicated items, such as in directory structures in filesystems.
• Version Stamps allow tracking of a variable number of replicas and do not resort to counters. This mechanism can depict scalability problems in some settings, but can be replaced by Interval Tree Clocks.
• Interval Tree Clocks generalize version vectors and vector clocks and allows dynamic numbers of replicas/processes.
• Bounded Version Vectors allow a bounded implementation, with bounded size counters, as long as replica pairs can be atomically synchronized.