Question: Explain the Lamport$'$s happens before relation along with the conditions. How are Lamport's logical clocks implemented?

Mumbai University > Information Technology > Sem6 > Distributed System

Marks: 10M

Year: May 2015

modified 3.4 years ago  • written 3.4 years ago by gravatar for Ramnath Ramnath3.8k
  • In synchronize logical clocks lamport defined a relation called happens-before.
  • the happens-before relation can be observed directly in two situations.

    1) If a and b are events in same process and a occurs before b, the a→ b is true. 2) If a is the event of a message being sent by another process then a→ b is also true. 3) A message cannot be received before it is sent, even at the same time it is sent , since it takes a finite(non-zero) amount of time to arrive. 4) The happen-before is a transitive relation so if a→ b & b→ c then a→ c. 5) If two events, x & y happen in different processes that do not exchange message, then x→ y

    is not true but neither is y →x.

6) the events are said to be concurrent which simply means that nothing can be said about when the event happened which event happened first.

enter image description here

a) 3-process each with its own clock, the b) Lamport algorithm corrects the clocks run at different rates. clocks.

7) Using these method , there is a way to assign time to all events in a distributed system subject to the following condition.

  • If a and b represent to sending and receiving of a message, respectively c(a)>c(b),
  • If a happens before b in the same process, c(a)<c(b)< li="">
  • for all distinctive event a and b,

    e.g. totally ordered multicasting.

written 3.4 years ago by gravatar for Ramnath Ramnath3.8k
Please log in to add an answer.