Vector clock

Lamport originated the idea of logical Lamport clocks in 1978.^[2] 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.^[3] At least 6 papers contain the concept.^[4] The papers canonically cited in reference to vector clocks are Colin Fidge’s and Friedemann Mattern’s 1988 works,^[5][6] as they (independently) established the name "vector clock" and the mathematical properties of vector clocks.^[3]

Vector clocks allow for the partial causal ordering of events. Defining the following:

• ${\displaystyle VC(x)}$ denotes the vector clock of event ${\displaystyle x}$ , and ${\displaystyle VC(x)_{z}}$ denotes the component of that clock for process ${\displaystyle 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'}]}$
  • In English: ${\displaystyle VC(x)}$ is less than ${\displaystyle VC(y)}$ , if and only if ${\displaystyle VC(x)_{z}}$ is less than or equal to ${\displaystyle VC(y)_{z}}$ for all process indices ${\displaystyle z}$ , and at least one of those relationships is strictly smaller (that is, ${\displaystyle VC(x)_{z'}<VC(y)_{z'}}$ ).
• ${\displaystyle x\to y\;}$ denotes that event ${\displaystyle x}$ happened before event ${\displaystyle y}$ . It is defined as: if ${\displaystyle x\to y\;}$ , then ${\displaystyle VC(x)<VC(y)}$

Properties:

• Antisymmetry: if ${\displaystyle VC(a)<VC(b)}$ , then ¬${\displaystyle (VC(b)<VC(a))}$
• Transitivity: if ${\displaystyle VC(a)<VC(b)}$ and ${\displaystyle VC(b)<VC(c)}$ , then ${\displaystyle VC(a)<VC(c)}$ ; or, if ${\displaystyle a\to b\;}$ and ${\displaystyle b\to c\;}$ , then ${\displaystyle a\to c\;}$

Relation with other orders:

• Let ${\displaystyle RT(x)}$ be the real time when event ${\displaystyle x}$ occurs. If ${\displaystyle VC(a)<VC(b)}$ , then ${\displaystyle RT(a)<RT(b)}$
• Let ${\displaystyle C(x)}$ be the Lamport timestamp of event ${\displaystyle x}$ . If ${\displaystyle VC(a)<VC(b)}$ , then ${\displaystyle C(a)<C(b)}$

• In 1999, Torres-Rojas and Ahamad developed Plausible Clocks,^[7] a mechanism that takes less space than vector clocks but that, in some cases, will totally order events that are causally concurrent.

• In 2005, Agarwal and Garg created Chain Clocks,^[8] 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.
• In 2008, Almeida et al. introduced Interval Tree Clocks.^[9][10][11] 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.

• In 2019, Lum Ramabaja proposed Bloom Clocks, a probabilistic data structure based on Bloom filters.^[12][13][14] 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.

• Lamport timestamps
• Matrix clocks
• Version vector

• Why Logical Clocks are Easy (Compares Causal Histories, Vector Clocks and Version Vectors)
• Explanation of Vector clocks
• Timestamp-based vector clock implementation in Erlang
• Vector clock implementation in Objective-C
• Vector clock implementation in Erlang
• Why Vector Clocks are Hard
• Why Cassandra doesn’t need vector clocks