Mumbai University > Information Technology > Sem 6 > Distributed System

Marks: 10Marks

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.