Clocks: Logical Clocks(II)

Vector clocks are an extension of Lamport clocks, where each node knows about the logical time of all the other nodes.

Prerequisites:

Clocks: It’s not that simple!

Clocks: Physical Clock Synchronization

Clocks: Logical Clocks

In my last article, we learned about Lamport Clocks and we saw how Lamport clocks can help us define ordering between our operations. However, given Lamport times( L(A) < L(B) ), we cannot tell whether A happened before B or A and B happened concurrently. It only tells us that B did not happen before A.

If we need to determine whether A happened before B, or the events were concurrent, we need to use Vector Clocks.

Vector Clocks

To explain in simple terms, Vector clocks are an extension of Lamport clocks, where each node knows about the logical time of all the other nodes. (Remember that in the Lamport Clock system, each node managed its clock independently and only knew about the logical time of the node it was receiving the message from).

Following are the steps followed by the algorithm -

1. Initialize the value of the array of counters to X, for each node/process. Each node/process holds an array of counters, representing the logical clock of every other node as well as itself.

2. For every event that a node/process receives locally, it increments the counter of the corresponding element in the array.

3. Each node/process can also send an event to another node/process. Before sending an event to another node/process, the counter of the corresponding element in the array is incremented and the incremented value of the counter is passed along with the event/message i.e. (<Ci, Cj….Cn>, M).

4. Each node when receiving a message/event from another node, gets the entire array of logical times from the source node, i.e. (<Ci, Cj,…Cn>, M). For each element in the local array, the destination process checks the value and checks for each counter value Ci, where i = 1 to n, in the array received with the message, and updates the counter value Ci to MAX(Ci from local, Ci from remote node) + 1 & then delivers the message to the concerned application.

Vector Clock Sync Algorithm

Using the above image, we can derive the following -

1. Given any two vector clocks, associated with different nodes/processes, if all elements of Vi are less than Vj, then Vi happened before Vj.

2. Given any two vector clocks, associated with different nodes/processes, if all elements of Vi are greater than Vj, then Vj happened before Vi.

3. If all elements of Vi and Vj are the same, then Vi and Vj can be considered identical vector clocks.

4. If some elements of Vi are less than some elements of Vj, and some elements of Vi are greater than some elements of Vj, Vi and Vj are said to be concurrent i.e. they happened in the same time window.

If you notice the vector clocks associated with any events, they represent the logical clocks associated with the event, as well as include the state of any event before it, i.e. the causal events. Eg — <2,2,0> represents the state when 2 events are received on node 1 and node 2, and none on node 3.

---

This brings us to the end of this article. We learned that Vector Clocks can help in establishing the ordering of operations, including identifying whether operations happened concurrently or were causally related. We’ll cover two more topics are part of this series, the next one on Versioned Vectors, which are very close to vector clocks!