Mumbai University > Information Technology > Sem6 > Distributed System

Marks: 10M

Year: Dec 2015

Lamport:

• To synchronize logical clocks Lamport defined a relation called happens-before.

• The Happen-Before relation can be observed directly in two situations.

  1) If A & B are events in same process and A occurs before B, then A → B is true.

  2) If A is the event of msg being send by one process and B is the event of msg being sent by another process then A→B is also true.

  A msg cannot be received before it is sent, or even at the same time it is sent, since it take a finite,(non-zero) amount of time to arrive.

• The Happen-Before is a transitive relation, so if A→B & B→C then A→C.

• If 2 events, X & Y happens in different processes that do not exchange message ,then X→Y is not true but neither Y→X.

• These events are said to be concurrent which simply means that nothing can be said about when the event happened or which event happened first.

  Using this method, there is a way to assign time to all events in distributed systems subjects to the following conditions,

• If a happens before b in the same process, c(a)<c(b).< p="">

• If a & b represent to sending and receiving of a message, respectively c(a) < c(b).
• For all distinctive, event a & b ,c(a)= c(b).
• E.g. Totally-Ordered Multicasting.