Logical Clocks(II) — Clock Series

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 Lamport Clock system, each node managed it’s clock independently and only knew about the logical time of the node its 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 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…