Vector Clocks

Limitation of Lamport clocks

The main limitation of Lamport clocks is that they do not satisfy the strong clock condition. This means they cannot be used to infer causal relationships between events.

The underlying reason for this is that both the local and the global logical clocks for each node are flattened into a single number, which does not provide all the necessary information to track causal relationships.

So we need to maintain a set of all events that causally precede each event. This is known as a causal historyS. Reinhard and M. Friedemann, “Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail,” Distributed Computing, Volume 7 Issue 3, March 1994, 1994.. For instance, the following illustration shows the causal history of $E_7$ is $\lbrace E_1, E_2, E_3, E_4, E_5\rbrace$. We also need to store the causal history of each event as efficiently as possible by using a compact data structure. According to Colin J.F. Colin J., “Timestamps in Message-Passing Systems That Preserve the Partial Ordering,” Proceedings of the 11th Australian Computer Science Conference (ACSC’88), pp. 56–66, 1988. and FriedemannM. Friedemann, “Virtual Time and Global States of Distributed Systems,” Parallel and Distributed Algorithms, 1988., a vector clock is an example of such a data structure.

Defining vector clock

A vector clock is another type of logical clock, where the clock data structure for each node is a vector of $N$ counters $[c^0, c^1, .., c^N]$, where $N$ is the number of nodes in the system. For the clock of the $i^{th}$ node $[{c_{i}}^0, {c_{i}}^1, ..., {c_{i}}^N]$:

• The $i^{th}$

...