This question appears in Mumbai University > Parallel And Distributed System subject

Marks: 10 M

Year: Dec 14

• To synchronize logical clocks, Lamport defined a relation called happens-before.
• The expression a ->b is read as ‘a happens before b’ and means that all processes agree that event a occurs then event b occurs.
• From the definition of the happened-before relation, the clock condition mentioned above is satisfied if the following conditions hold:

i.C1- If a and b are two events within the same process Pi and a occurs before then Ci(a) <ci(b).< p="">

ii.C2- If a is message sent by process Pi and b is the receipt of that message by process Pj then Ci(a) <ci(b).< p="">

iii.C3- A clock Ci associated with a process Pi must always go forward, never backward. Correction to time of a logical clock must always be made by positive value not by subtracting.

• First two conditions are needed to satisfy clock condition while the third is needed for correct functioning of the system.
• Any algorithm used for implementing a set of logical clocks must satisfy all three conditions proposed by Lamport.
• The algorithm for assigning time to events using physical and logical clocks depending on the above conditions is as follows.

• Consider two processes in fig (a) the processes run on different machines each having a physical clock associated with it running at its own speed. For process Po the time ticked is 6 times and process P1 has the time ticked 8 times. The clocks run at constant rate but are different due to difference in the crystals.
• At time 6, Po sends message A to P1 and is received at time 16. Consider the time taken for message transfer as 10 is considerable.
• Now when Message B is sent from P2 at time 64 it takes 10 ticks to reach P1. So the message is received at time 54 by P1 because the time for P1 is slower. This value is certainly impossible and such a situation must be prevented.
• The solution for this is given by Lamports happens-before relation. Since B left at 64 it must arrive at 65 or later. There for the message also carries the sending time according to sender’s clock.
• When a message arrives and the receiver’s clock shows a prior value to the time the message was sent, the receiver fast forwards its clock to be one more than the sending time.
• In fig (b) we can see that message C now arrives at 65. With one small addition this algorithm meets the requirements for global time.
• This algorithm provides total ordering of all events in the system.