Vector clocks algorithms are used in distributed systems to provide a causally consistent ordering of events but the entire Vector is sent to each process for every message sent, in order to keep the vector clocks in sync.
Let’s try to understand mechanism of vector clock.
- Initially all clocks are zero.
- Each time a process experiences an internal event, it increments its own logical clock in the vector by one. For instance, upon an event at process i, it updates Vector Clock i = Vector Clock i + 1
- Each time a process sends a message, it increments its own logical clock in the vector by one and then the message piggybacks a copy of its own vector.
- Each time a process receives a message, it increments its own logical clock in the vector by one and 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 (for every element)
Let’s try to understand vector clock mechanism with one another explanation.
The rule for incrementing the timestamp for the vector clock is also similar to Lamport’s clock with a small addition to it. The events update the logical timestamp according to the below rules:
- Before executing an event, the process i increments the i-th element of its vector clock by 1
V[i] = V[i] + 1
2. During a send event, the process i increments the i-th element of its vector clock by 1 and sends the time(Vmsg[1…N]) along with the message.
V[i] = V[i] + 1
3. During a receive event, the process i increments the i-th element of its vector clock by 1. For all other processes, it takes the maximum of the corresponding element in the incoming message and its own local vector and sets it as the corresponding element in the local clock itself.
V[i] = V[i] + 1V[j] = max(Vmsg[j], V[j]) for j ≠ i
We can use the vector timestamps to verify if two events are either causally related or concurrent. Before that, we will see how two vector timestamps are compared.
We are sorry that this post was not useful for you!
Let us improve this post!
Tell us how we can improve this post?