Vector clock

• Initially all clocks are zero.
• Each time a process experiences an internal event, it increments its own logical clock in the vector by one.
• Each time a process sends a message, it increments its own logical clock in the vector by one and then sends a copy of its own vector.
• Each time a process receives a message, it increments its own logical clock in the vector by one and updates each element in its vector by taking the maximum of the value in its own vector clock and the value in the vector in the received message.

Partial ordering property

• denotes the vector clock of event, and denotes the component of that clock for process.
• * In English: is less than, if and only if is less than or equal to for all process indices, and at least one of those relationships is strictly smaller.
• denotes that event happened before event. It is defined as: if, then

• Antisymmetry: if, then ¬
• Transitivity: if and, then or if and, then

• Let be the real time when event occurs. If, then
• Let be the Lamport timestamp of event. If, then

  Other mechanisms

• In 1999, Torres-Rojas and Ahamad developed Plausible Clocks, a mechanism that takes less space than vector clocks but that, in some cases, will totally order events that are causally concurrent.
• In 2008, Almeida et al. introduced Interval Tree Clocks. 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 developed Bloom Clocks, a probabilistic data structure whose space complexity does not depend on the number of nodes in a system. If two clocks are not comparable, the bloom clock can always deduce it, i.e. false negatives are not possible. If two clocks are comparable, the bloom clock can calculate the confidence of that statement, i.e. it can compute the false positive rate between comparable pairs of clocks.