Vector clock

<h2 id="history">History</h2>
Lamport originated the idea of logical <a href="/facts/Lamport_clock/Dpxw6Ia4">Lamport clocks</a> in 1978.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> However, the logical clocks in that paper were scalars, not vectors. The generalization to vector time was developed several times, apparently independently, by different authors in the early 1980s.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> At least 6 papers contain the concept.
<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> The papers canonically cited in reference to vector clocks are Colin Fidge’s and <a href="/facts/Friedemann_Mattern/wu1nga9k">Friedemann Mattern</a>’s 1988 works,
<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> as they (independently) established the name "vector clock" and the mathematical properties of vector clocks.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="partial-ordering-property">Partial ordering property</h2>
Vector clocks allow for the partial causal ordering of events. Defining the following:

<ul><li>
 
 
 
 V
 C
 (
 x
 )
 
 
 {\displaystyle VC(x)}
 
 denotes the vector clock of event 
 
 
 
 x
 
 
 {\displaystyle x}
 
, and 
 
 
 
 V
 C
 (
 x
 
 )
 
 z
 
 
 
 
 {\displaystyle VC(x)_{z}}
 
 denotes the component of that clock for process 
 
 
 
 z
 
 
 {\displaystyle z}
 
.</li>
<li>
 
 
 
 V
 C
 (
 x
 )
 <
 V
 C
 (
 y
 )
 
 ⟺
 
 ∀
 z
 [
 V
 C
 (
 x
 
 )
 
 z
 
 
 ≤
 V
 C
 (
 y
 
 )
 
 z
 
 
 ]
 ∧
 ∃
 
 z
 ′
 
 [
 V
 C
 (
 x
 
 )
 
 
 z
 ′
 
 
 
 <
 V
 C
 (
 y
 
 )
 
 
 z
 ′
 
 
 
 ]
 
 
 {\displaystyle VC(x)<VC(y)\iff \forall z[VC(x)_{z}\leq VC(y)_{z}]\land \exists z'[VC(x)_{z'}<VC(y)_{z'}]}

<ul><li>In English: 
 
 
 
 V
 C
 (
 x
 )
 
 
 {\displaystyle VC(x)}
 
 is less than 
 
 
 
 V
 C
 (
 y
 )
 
 
 {\displaystyle VC(y)}
 
, if and only if 
 
 
 
 V
 C
 (
 x
 
 )
 
 z
 
 
 
 
 {\displaystyle VC(x)_{z}}
 
 is less than or equal to 
 
 
 
 V
 C
 (
 y
 
 )
 
 z
 
 
 
 
 {\displaystyle VC(y)_{z}}
 
 for all process indices 
 
 
 
 z
 
 
 {\displaystyle z}
 
, and at least one of those relationships is strictly smaller (that is, 
 
 
 
 V
 C
 (
 x
 
 )
 
 
 z
 ′
 
 
 
 <
 V
 C
 (
 y
 
 )
 
 
 z
 ′
 
 
 
 
 
 {\displaystyle VC(x)_{z'}<VC(y)_{z'}}
 
).</li></ul></li>
<li>
 
 
 
 x
 →
 y
 
 
 
 {\displaystyle x\to y\;}
 
 denotes that event 
 
 
 
 x
 
 
 {\displaystyle x}
 
 happened before event 
 
 
 
 y
 
 
 {\displaystyle y}
 
. It is defined as: if 
 
 
 
 x
 →
 y
 
 
 
 {\displaystyle x\to y\;}
 
, then 
 
 
 
 V
 C
 (
 x
 )
 <
 V
 C
 (
 y
 )
 
 
 {\displaystyle VC(x)<VC(y)}
 
</li></ul>
Properties:

<ul><li><a href="/facts/Antisymmetric_relation/YhuqG4z8">Antisymmetry</a>: if 
 
 
 
 V
 C
 (
 a
 )
 <
 V
 C
 (
 b
 )
 
 
 {\displaystyle VC(a)<VC(b)}
 
, then ¬
 
 
 
 (
 V
 C
 (
 b
 )
 <
 V
 C
 (
 a
 )
 )
 
 
 {\displaystyle (VC(b)<VC(a))}
 
</li>
<li><a href="/facts/Transitive_relation/9r90y50r">Transitivity</a>: if 
 
 
 
 V
 C
 (
 a
 )
 <
 V
 C
 (
 b
 )
 
 
 {\displaystyle VC(a)<VC(b)}
 
 and 
 
 
 
 V
 C
 (
 b
 )
 <
 V
 C
 (
 c
 )
 
 
 {\displaystyle VC(b)<VC(c)}
 
, then 
 
 
 
 V
 C
 (
 a
 )
 <
 V
 C
 (
 c
 )
 
 
 {\displaystyle VC(a)<VC(c)}
 
; or, if 
 
 
 
 a
 →
 b
 
 
 
 {\displaystyle a\to b\;}
 
 and 
 
 
 
 b
 →
 c
 
 
 
 {\displaystyle b\to c\;}
 
, then 
 
 
 
 a
 →
 c
 
 
 
 {\displaystyle a\to c\;}
 
</li></ul>
Relation with other orders:

<ul><li>Let 
 
 
 
 R
 T
 (
 x
 )
 
 
 {\displaystyle RT(x)}
 
 be the real time when event 
 
 
 
 x
 
 
 {\displaystyle x}
 
 occurs. If 
 
 
 
 V
 C
 (
 a
 )
 <
 V
 C
 (
 b
 )
 
 
 {\displaystyle VC(a)<VC(b)}
 
, then 
 
 
 
 R
 T
 (
 a
 )
 <
 R
 T
 (
 b
 )
 
 
 {\displaystyle RT(a)<RT(b)}
 
</li>
<li>Let 
 
 
 
 C
 (
 x
 )
 
 
 {\displaystyle C(x)}
 
 be the <a href="/facts/Lamport_timestamps/Dpxw6Ia4">Lamport timestamp</a> of event 
 
 
 
 x
 
 
 {\displaystyle x}
 
. If 
 
 
 
 V
 C
 (
 a
 )
 <
 V
 C
 (
 b
 )
 
 
 {\displaystyle VC(a)<VC(b)}
 
, then 
 
 
 
 C
 (
 a
 )
 <
 C
 (
 b
 )
 
 
 {\displaystyle C(a)<C(b)}
 
</li></ul>
<h2 id="other-mechanisms">Other mechanisms</h2>

<ul><li>In 1999, Torres-Rojas and Ahamad developed Plausible Clocks,<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> a mechanism that takes less space than vector clocks but that, in some cases, will totally order events that are causally concurrent.</li></ul>
<ul><li>In 2005, Agarwal and Garg created Chain Clocks,<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> a system that tracks dependencies using vectors with size smaller than the number of processes and that adapts automatically to systems with dynamic number of processes.</li>
<li>In 2008, Almeida et al. introduced Interval Tree Clocks.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> This mechanism generalizes Vector Clocks and allows operation in dynamic environments when the identities and number of processes in the computation is not known in advance.</li></ul>
<ul><li>In 2019, Lum Ramabaja proposed Bloom Clocks, a probabilistic data structure based on <a href="/facts/Bloom_filters/Gq2WVE37">Bloom filters</a>.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a><a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> Compared to a vector clock, the space used per node is fixed and does not depend on the number of nodes in a system. Comparing two clocks either produces a true negative (the clocks are not comparable), or else a suggestion that one clock precedes the other, with the possibility of a false positive where the two clocks are unrelated. The false positive rate decreases as more storage is allowed.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Lamport_timestamps/Dpxw6Ia4">Lamport timestamps</a></li>
<li><a href="/facts/Matrix_clock/7u3EnonE">Matrix clocks</a></li>
<li><a href="/facts/Version_vector/U96FfE1p">Version vector</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://queue.acm.org/detail.cfm?id=2917756">Why Logical Clocks are Easy (Compares Causal Histories, Vector Clocks and Version Vectors)</a></li>
<li><a href="http://basho.com/why-vector-clocks-are-easy/">Explanation of Vector clocks</a></li>
<li><a href="https://github.com/cliffmoon/dynomite/blob/master/elibs/vector_clock.erl">Timestamp-based vector clock implementation in Erlang</a></li>
<li><a href="https://github.com/jeremytregunna/JVectorClock">Vector clock implementation in Objective-C</a></li>
<li><a href="https://github.com/basho/riak_core/blob/master/src/vclock.erl">Vector clock implementation in Erlang</a></li>
<li><a href="http://basho.com/why-vector-clocks-are-hard/">Why Vector Clocks are Hard</a></li>
<li><a href="http://www.datastax.com/dev/blog/why-cassandra-doesnt-need-vector-clocks">Why Cassandra doesn’t need vector clocks</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"Distributed Systems 3rd edition (2017)". DISTRIBUTED-SYSTEMS.NET. Retrieved 2021-03-21. <a href="https://www.distributed-systems.net/index.php/books/ds3/" target="_blank">https://www.distributed-systems.net/index.php/books/ds3/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Lamport, L. (1978). "Time, clocks, and the ordering of events in a distributed system" (PDF). Communications of the ACM . 21 (7): 558–565. doi:10.1145/359545.359563. S2CID 215822405. <a href="/wiki/Leslie_Lamport" target="_blank">/wiki/Leslie_Lamport</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Schwarz, Reinhard; Mattern, Friedemann (March 1994). "Detecting causal relationships in distributed computations: In search of the holy grail". Distributed Computing. 7 (3): 149–174. doi:10.1007/BF02277859. S2CID 3065996. <a href="https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-4006" target="_blank">https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-4006</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Kuper, Lindsey (8 April 2023). "Who invented vector clocks?". decomposition ∘ al. The papers are (in chronological order):
Fischer, Michael J.; Michael, Alan (1982). "Sacrificing serializability to attain high availability of data in an unreliable network". Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems - PODS '82. p. 70. doi:10.1145/588111.588124. ISBN 0897910702. S2CID 8774876.
Parker, D.S.; Popek, G.J.; Rudisin, G.; Stoughton, A.; Walker, B.J.; Walton, E.; Chow, J.M.; Edwards, D.; Kiser, S.; Kline, C. (May 1983). "Detection of Mutual Inconsistency in Distributed Systems". IEEE Transactions on Software Engineering. SE-9 (3): 240–247. doi:10.1109/TSE.1983.236733. S2CID 2483222.
Wuu, Gene T.J.; Bernstein, Arthur J. (1984). "Efficient solutions to the replicated log and dictionary problems". Proceedings of the third annual ACM symposium on Principles of distributed computing - PODC '84. pp. 233–242. doi:10.1145/800222.806750. ISBN 0897911431. S2CID 2384672.
Strom, Rob; Yemini, Shaula (August 1985). "Optimistic recovery in distributed systems". ACM Transactions on Computer Systems. 3 (3): 204–226. doi:10.1145/3959.3962. S2CID 1941122.
Schmuck, Frank B. (November 1985). Software clocks and the order of events in a distributed system (unpublished).
Liskov, Barbara; Ladin, Rivka (1986). "Highly available distributed services and fault-tolerant distributed garbage collection". Proceedings of the fifth annual ACM symposium on Principles of distributed computing - PODC '86. pp. 29–39. doi:10.1145/10590.10593. ISBN 0897911989. S2CID 16148617.
Raynal, Michel (February 1987). "A distributed algorithm to prevent mutual drift between n logical clocks". Information Processing Letters. 24 (3): 199–202. doi:10.1016/0020-0190(87)90186-4.
 <a href="089791070208979114310897911989" target="_blank">089791070208979114310897911989</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Fidge, Colin J. (February 1988). "Timestamps in message-passing systems that preserve the partial ordering" (PDF). In K. Raymond (ed.). Proceedings of the 11th Australian Computer Science Conference (ACSC'88). Vol. 10. pp. 56–66. Retrieved 2009-02-13. <a href="http://zoo.cs.yale.edu/classes/cs426/2012/lab/bib/fidge88timestamps.pdf" target="_blank">http://zoo.cs.yale.edu/classes/cs426/2012/lab/bib/fidge88timestamps.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Mattern, Friedemann (October 1988). "Virtual Time and Global States of Distributed systems". In Cosnard, M. (ed.). Proc. Workshop on Parallel and Distributed Algorithms. Chateau de Bonas, France: Elsevier. pp. 215–226. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Schwarz, Reinhard; Mattern, Friedemann (March 1994). "Detecting causal relationships in distributed computations: In search of the holy grail". Distributed Computing. 7 (3): 149–174. doi:10.1007/BF02277859. S2CID 3065996. <a href="https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-4006" target="_blank">https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-4006</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Francisco Torres-Rojas; Mustaque Ahamad (1999), "Plausible clocks: constant size logical clocks for distributed systems", Distributed Computing, 12 (4): 179–195, doi:10.1007/s004460050065, S2CID 2936350 <a href="https://www.cc.gatech.edu/fac/Mustaque.Ahamad/pubs/plausible.ps" target="_blank">https://www.cc.gatech.edu/fac/Mustaque.Ahamad/pubs/plausible.ps</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Agarwal, Anurag; Garg, Vijay K. (17 July 2005). "Efficient dependency tracking for relevant events in shared-memory systems" (PDF). Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing. Association for Computing Machinery. pp. 19–28. doi:10.1145/1073814.1073818. ISBN 1-58113-994-2. S2CID 11779779. Retrieved 21 April 2021. <a href="1-58113-994-2" target="_blank">1-58113-994-2</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008), "Interval Tree Clocks: A Logical Clock for Dynamic Systems", in Baker, Theodore P.; Bui, Alain; Tixeuil, Sébastien (eds.), Principles of Distributed Systems (PDF), Lecture Notes in Computer Science, vol. 5401, Springer-Verlag, Lecture Notes in Computer Science, pp. 259–274, Bibcode:2008LNCS.5401.....B, doi:10.1007/978-3-540-92221-6, ISBN 978-3-540-92220-9 <a href="978-3-540-92220-9" target="_blank">978-3-540-92220-9</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008), "Interval Tree Clocks: A Logical Clock for Dynamic Systems", Interval Tree Clocks: A Logical Clock for Dynamic Systems, Lecture Notes in Computer Science, vol. 5401, p. 259, doi:10.1007/978-3-540-92221-6_18, hdl:1822/37748, ISBN 978-3-540-92220-9 <a href="978-3-540-92220-9" target="_blank">978-3-540-92220-9</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Zhang, Yi (2014), "Background Preliminaries: Interval Tree Clock Results", Background Preliminaries: Interval Tree Clock Results (PDF) <a href="https://cs.uwaterloo.ca/~mkarsten/cs755-F14/presentations/ITC.pdf" target="_blank">https://cs.uwaterloo.ca/~mkarsten/cs755-F14/presentations/ITC.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Pozzetti, Tommaso; Kshemkalyani, Ajay D. (1 April 2021). "Resettable Encoded Vector Clock for Causality Analysis With an Application to Dynamic Race Detection". IEEE Transactions on Parallel and Distributed Systems. 32 (4): 772–785. doi:10.1109/TPDS.2020.3032293. S2CID 220362525. <a href="https://doi.org/10.1109%2FTPDS.2020.3032293" target="_blank">https://doi.org/10.1109%2FTPDS.2020.3032293</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Lum Ramabaja (2019), The Bloom Clock, arXiv:1905.13064, Bibcode:2019arXiv190513064R <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Kulkarni, Sandeep S; Appleton, Gabe; Nguyen, Duong (4 January 2022). "Achieving Causality with Physical Clocks". Proceedings of the 23rd International Conference on Distributed Computing and Networking. pp. 97–106. arXiv:2104.15099. doi:10.1145/3491003.3491009. ISBN 9781450395601. S2CID 233476293. <a href="9781450395601" target="_blank">9781450395601</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
</ol>

Vector clock open-in-new

Vector clock