# Version vector

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Version_vector
> Markdown URL: https://mediated.wiki/source/Version_vector.md
> Source: https://en.wikipedia.org/wiki/Version_vector
> Source revision: 1340545730
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Mechanism for tracking data changes}}
{{confuse|Vector clock}}
A '''version vector''' is a mechanism for tracking changes to data in a [distributed system](/source/distributed_system), where multiple agents might update the data at different times. The version vector allows the participants to determine if one update preceded another ([happened-before](/source/happened-before)), followed it, or if the two updates happened concurrently (and therefore might conflict with each other). In this way, version vectors enable [causality](/source/causality) tracking among data replicas and are a basic mechanism for [optimistic replication](/source/optimistic_replication).  In mathematical terms, the version vector generates a [preorder](/source/preorder) that tracks the events that precede, and may therefore influence, later updates.

Version vectors maintain state identical to that in a [vector clock](/source/vector_clock), but the update rules differ slightly;  in this example, replicas can either experience local updates (e.g., the user editing a file on the local node), or can synchronize with another replica:

* Initially all vector counters are zero.
* Each time a replica experiences a local update event, it increments its own counter in the vector by one.
* Each time two replicas {{mvar|a}} and {{mvar|b}} synchronize, they both set the elements in their copy of the vector to the maximum of the element across both counters:  <math>V_a[x] = V_b[x] = \max(V_a[x], V_b[x])</math>.  After synchronization, the two replicas have identical version vectors.

Pairs of replicas, {{mvar|a}}, {{mvar|b}}, can be compared by inspecting their version vectors and determined to be either: identical (<math>a=b</math>), concurrent (<math>a \parallel b</math>), or ordered (<math>a < b</math> or <math>b < a</math>).  The ordered relation is defined as:  Vector <math>a < b</math> if and only if every element of <math>V_a</math> is less than or equal to its corresponding element in <math>V_b</math>, and at least one of the elements is strictly less than.  If neither <math>a < b</math> or <math>b < a</math>, but the vectors are not identical, then the two vectors must be concurrent.

Version vectors<ref>Douglas Parker, Gerald Popek, Gerard Rudisin, Allen Stoughton, Bruce Walker, Evelyn Walton,  Johanna Chow, David Edwards, Stephen Kiser, and [Charles Kline](/source/Charles_S._Kline). Detection of mutual inconsistency in distributed systems. Transactions on Software Engineering. 1983</ref> or variants are used to track updates in many distributed file systems, such as  [Coda (file system)](/source/Coda_(file_system)) and Ficus, and are the main [data structure](/source/data_structure) behind optimistic replication.<ref>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</ref>

==Other mechanisms==
* Hash Histories <ref>ByungHoon Kang, Robert Wilensky, and John Kubiatowicz.
The Hash History Approach for Reconciling Mutual Inconsistency. 
ICDCS, pp. 670-677, IEEE Computer Society, 2003.</ref> 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 guarantees.
* Concise Version Vectors <ref>[Dahlia Malkhi](/source/Dahlia_Malkhi) and Doug Terry. Concise Version Vectors in WinFS.Distributed Computing, Vol. 20, 2007.</ref> allow significant space savings when handling multiple replicated items, such as in directory structures in filesystems.
* Version Stamps <ref>Paulo Almeida, Carlos Baquero and Victor Fonte. Version Stamps: Decentralized Version Vectors. ICDCS, pp. 544-551, 2002.</ref> 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](/source/Interval_tree) Clocks.
* Interval Tree Clocks<ref>Paulo Almeida, Carlos Baquero and Victor Fonte. Interval Tree Clocks. OPODIS, Lecture Notes in Computer Science, Vol. 5401, pp. 259-274, Springer, 2008.</ref> generalize version vectors and vector clocks and allows dynamic numbers of replicas/processes.
* Bounded Version Vectors  <ref>José Almeida, Paulo Almeida and Carlos Baquero. Bounded Version Vectors. DISC: International Symposium on Distributed Computing, LNCS, 2004.</ref> allow a bounded implementation, with bounded size counters, as long as replica pairs can be atomically synchronized.
* Dotted Version Vectors <ref>Nuno Preguiça, Carlos Baquero, Paulo Almeida, Victor Fonte and Ricardo Gonçalves. Brief Announcement: Efficient Causality Tracking in Distributed Storage Systems With Dotted Version Vectors. ACM PODC, pp. 335-336, 2012.</ref> address scalability with a small set of servers mediating replica access by a large number of concurrent clients.

==References==
{{reflist}}

== External links ==
* [http://queue.acm.org/detail.cfm?id=2917756 Why Logical Clocks are Easy (Compares Causal Histories, Vector Clocks and Version Vectors)]

Category:Data synchronization
Category:Logical clock algorithms
Category:Distributed computing problems

---
Adapted from the Wikipedia article [Version vector](https://en.wikipedia.org/wiki/Version_vector) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Version_vector?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.