Logical Clocks(II) — Clock Series

In my last article, we learned about Lamport Clocks and we saw how Lamport clocks could 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 its clock independently and only knew about the logical time of the node it's 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 the remote node) + 1 & then delivers the message to the concerned application.

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!

Thank you for reading! I’ll be posting weekly content on distributed systems & patterns, so please like, share and subscribe to this?newsletter?for notifications of new posts.

Please comment on the post with your feedback, will help me improve! :)

Until next time, Keep asking questions & Keep learning!