Vector Clocks

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}$ element of the clock ${c_{i}}^i$ represents the local logical clock of the node
• The remaining elements of the clock $[{c_{i}}^0, ..., {c_{i}}^{i-1}, {c_{i}}^{i+1},..., {c_{i}}^N]$ together form the global logical clock of the node

Rules of the protocol

The rules of the protocol are the following:

• (R1) Before executing an event (send, receive, or local), a node increments the counter of its logical clock by one: ${C_{i}}^i = {C_{i}}^i + 1$.
• (R2) Every sent message piggybacks the clock value of its sender at sending time. When the $i^{th}$ node receives a message with a vector $[{c_{j}}^0, ..., {c_{j}}^N]$ from the $j^{th}$ node, it executes the following actions:
  • Executes R1
  • 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: ${C_{i}}^k = max({c_{i}}^k, {c_{j}}^k)$ for every $k$ in $[0, N]$
  • Delivers the message

Strong clock condition

Vector clock satisfies the strong clock condition. This means that if the relationship C​i<C​j​​ holds for two events $E_i$, $E_j$ with timestamps $C_i$, then $E_i\to E_j$.’

The only missing thing is how comparing vector clocks with each other, which is done in the following way:

• For two clocks $C_i = [{c_{i}}^0, ..., {c_{i}}^N]$ and $C_j = [{c_{j}}^0, ..., {c_{j}}^N]$ $C_i < C_j$ iff all the elements of the clock $C_i$ are less than or equal to all the corresponding elements of clock $C_j$ $({c_{i}}^k \leq {c_{j}}^k$ for all $k)$ and there is at least one element of $C_i$ that is strictly smaller than the corresponding element of $C_j$ $({c_{i}}^l < {c_{j}}^l$ for at least one $l$ in $[0, N])$.

Working of vector clocks

The following illustration contains the same distributed execution displayed in the Lamport clocks lesson’s illustration. This time, we are using vector clocks.

Each node in the system maintains a vector clock, where the first element corresponds to the time in node $A$, the second to the time in node $B$, and the third and last element to the time in node $C$.

We can spend some time again verifying that the clock values have been assigned just by following the rules described above.

This time, we can see that the clock of $A_1$ is smaller than the clock of $B_1$, while also $A_1 \to B_1$.

What’s more important, though, is that we can detect events that are not causally related. For instance, $B_2 \parallel C_2$ and we can see that the timestamp of $B_2$ is neither smaller nor larger than the timestamp of $C_2$. This means that we can consider these events concurrent, and they could have happened in any order.

Usage of vector clocks

Vector clocks can be used in cases that benefit from the capability to detect whether two events are causally related or concurrent. They also allow the different nodes of the system to make progress independently and efficiently without synchronization and coordination bottlenecks.

Points to be noted

We mentioned previously that in a distributed system of $n$ nodes, each vector clock is composed of $n$ elements. It’s important to clarify that every process that consists of a source of concurrency needs to be considered as a node of the system in the context of the vector clocks. This means an entry for this process should be dedicated in each clock.

For example, if our application consists of three servers and two clients, each vector clock should contain five entries. Otherwise, we risk not being able to identify concurrent and conflicting operations, and treating them as causally related instead.

See why vector clocks are hard.

It has been formally proven by Charron-Bost et al.B. Charron-Bost, “Concerning the Size of Logical Clocks in Distributed Systems,” Information Processing Letters, Volume 39 Issue 1, July 12, 1991, 1991. that “the size of a vector clock must be at least $n$ for a system consisting of $n$ nodes to fully capture causality”. This means that vector clocks require a significant amount of storage in cases where the number of all the participating nodes is large. This can be the case for some types of systems nowadays, such as web applications where every browser is considered a client of the system.