Summerizing "Time,Clocks, and the Ordering of Events in a Distributed System" by Lamport.

In a distributed system, the message transmission delay between the distributed processes is not negligible compared to the time between the events in a single process; and it is sometimes impossible to say that one of the two events occurred first. The relationship is therefore merely a partial ordering of the events in the system.

The paper defines “happened before” relationship without using physical clocks - The system is assumed to be a collection of processes, each process containing a sequence of events.

The “happened before” relationship is denoted by “—>” and is satisfied by the following three conditions:

1) If a and b are events in the same process, and a comes before b, then a —> b

2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a—> b.

3) If a—>b and b—>c then a—>c. Two events a and b are said to be concurrent if a-/->b and b-/->a.

Also, obviously a-/-> a.

In other terms a—>b implies a causally affects b. Two concurrent events imply they are not causally affected.

Logical Clocks

A clock is just a number assigned to an event, where the number could the time at which the event occurred or something generated by a counter.

The correctness of the clock is then defined by the following condition:

For any events a. b: if a—>b then event_time<a> < event_time<b>

So if there are two processes in the system i and j, and their respective clocks represented as Ci and Cj, then:

If a nd b are events in process i, and a comes before b, then Ci<a> < Ci<b>

Of a is the sending of a message by process i and b is the receipt of the message by process j. then Ci<a> < Cj<b>.

Ordering and Synchronization

To define ordering in the system, we require that each message m contain a timestamp of when the message was sent. Upon the receipt of the message, the recipient process must advance its clock to be later than the timestamp in the message. The receive event is assigned this new adjusted time.