Vector clock algorithm

This algorithm is used to determine the partial ordering of events in a distributed system and also to detect casualty violations

1. Vector clock algorit hm Subject: Distributed systems Department of computer science and Engineering Prof. S. Anbu Sep’10, 2021

2. This algorithm is used to determine the partial ordering of events in a distributed system and also to detect causality violations.

3. What is Casualty violations ? Assume the processes are running P0,P1 and P2.

4. At 1’o clock, The first process P0 send a message to P1. This message reaches P1 only at 6 pm in the evening. At 2’0 clock, the first process P0 send an another message to the process p3. It reaches P3 at 3 pm. The processPp3 also sends one message to process P2 at 4 ‘o clock. This message reaches P1 at 5 pm.

5. The important thing about this situation is that , the message from P2 arrives at P1, before the first message from P0 reaches p1 i.e the first message arrives only at 6 pm. ( late arrival) This timing problem should be solved .

6. A simple e xample

7. The process P gives one apple to P 1 . Immediately P0 sends a message to P 2 that P 1 has one apple So P 2 sends a message to P 1 to eat that apple. But the real situation is, P 1 not yet received that apple. So how does he eat it?

8. This example illustrates a causality violation . A causality violation occurs when a message ordering problem results in one host taking an action based on information that another host should have received, but not yet received. In this case , P2 is trying to invoke a method ( eat( ) ) on P1, because P2 wrongly assumes that P1 has an apple.

9. Each process in a system should have knowledge of other processes running in the system to find the causality violations. i.e An array of knowledge is needed by each process. Lamport logical lock is not sufficient to solve this problem, because it tracks only the total number of events in the system So a new communication mechanism is needed to solve this causality violation problem. What is that mechanism? Vector clocks . Solution

10. Vector Clocks are used in a distributed systems to determine whether pairs of events are causally related or not. Using Vector Clocks, timestamps are generated for each event in the system, and their causal relationship is determined by comparing those timestamps . Vector clock of a system of N processes is an array of N logical clocks, i.e one clock per process. So for N given processes, there will be a vector/ array of size N . [ 1….N] Vector clocks

11. As with Lamport logical time, each process maintains its own view of the local time and updates it using the timestamps placed by the sender onto messages. But with vector logical time, the time contains more information i.e it contains a vector representing the state of each process running in the distributed system. In other words, this vector not only contains the event count for the process itself , it also contains the last-known event counts on each and every other process .

12. Initially , all the clocks are set to zero . Every time, an Internal event occurs in a process, the value of the processes' logical clock in the vector is incremented by 1 Two rules Rule 1 : ( Local update rule) Every time a process sends a message, the value of the processes' logical clock in the vector is incremented by 1 and and then send a copy of its own vector. Rule 2: (message rule) Every time, a process receives a message, the value of the processes' logical clock in the vector is incremented by 1. Moreover , each element is updated by taking the maximum of the value in its own vector clock and the value in the vector in the received message . Vector clock Algorithm

13. As a result, when a process receives a message, it merges its own time vector and the timestamp sent with the message -- it selects the higher of the values for each element. This ensures that the sender has information that is at least as up-to-date as the receiver .

14. How this algorithm works….

15. Assume, N = 3. i.e 3 processes are running p1, p2 and p3. Apply rule 1 ( Local update rule) The event a occurs in p1. So it increments its own logical clock in the vector by 1. ( 1,0,0) The event d occurs in p2. So it increments its own logical clock in the vector by 1. ( 0,1,0) The event g occurs in p3. So it increments its own logical clock in the vector by 1. ( 0,0,1)

16. Now , event b occurs in process p1. So again apply rule 1 (local update rule). Process p1 increments its clock in the vector by 1. ( 2,0,0).

17. The event b of process p1 sends a message to the event e in process p2. Also sends a copy of its own vector to p2( By piggybacking. i.e sends vector elements on the shoulder of message). Now what will be the status of the vector clocks ?.

18. Apply rule 2 ( Every time, a process receives a message, the value of the processes' logical clock in the vector is incremented by 1 . Moreover, each element is updated by taking the maximum of the value in its own vector clock and the value in the vector i n the received mess a g e ( for every element ) ) . First, Increment VC of p2 by 1 as per the rule. So ( 0,1,0) becomes ( 0,2,0) . Vector clock values in the received message are ( 2, 0, 0). ( Already sent by p1) Take maximum of these two vector clock values Time stamps ----------- 0, 2, 0 0 and 2 . maximum is 2 2, 0, 0 2 and 0 . maximum is 2 ----------- 2, 2, 0 ----------

19. Now the current status of all vector clocks are ( 2, 2, 0)

20. Now, m any events occur in all the processes Event h occurs in process p3 . So VCs become ( 0 , 0, 2 ) Event c occurs in process p1 . Now, VCs become ( 3, 0, 0) Event f occurs in process p2 . Now, VCs become ( 2 , 3, 0) Event i occurs in process p3.

21. Now event f of process p2 sends a message to event i of process p3 .

22. Now what will be the status of the vector clocks now ?. Apply rule 2 first, Increment VC of p3 by 1 as per the rule So ( 0, 0, 2) becomes ( 0, 0, 3 ) Vector clock values in the received message are ( Already sent by p2) ( 2, 3, 0). Take maximum of these two vector clock values Time stamps ------------ 0, 0, 3 take maximum values 2, 3, ----------- 2, 3, 3 ----------

23. Vector clocks easily captures the causality between inter-process communications. Partial order (→) between a and i.

24. If two events are not comparable, we say these events are concurrent . But L amport logical clock mechanism can not find whether the events are concurrent or not. This problem is solved by the vector clock mechanism Using vector clock, timestamps are created for each event in the distributed system and their relationship is determined by comparing those timestamps. Whether they are concurrent or in a casual relationship. Vector clock timestamps precisely capture happens-befor e relation Vector Clocks guarantee strong clock consistency as they are an extension of Lamport Timestamps. . Advantages of Vector clock mechanism

25. Thank you