Define Happened-Before Relationship. Explain implementation of logical clocks with an example

Mumbai University > Information Technology > Sem 6 > Distributed System

Marks: 10Marks

1 Answer


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.

enter image description here

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.

Please log in to add an answer.