Ordering events on distributed machines using logical clocks

A distributed system generally consists of a set of processes. These processes communicate with each other by sending messages. A process can also be viewed as a sequence of events occurring in an order.

In order to avoid synchronization problems in such an environment, it is important to determine the order of occurrence of events in a process or among different processes. A "happened before' relation can be used to provide a partial order for these events. Using physical clocks to define the ordering of events may not be the best approach as the physical clocks may not show perfectly accurate time. Therefore, the concept of logical clocks was introduced.

Happened before relationship:
The happened before relationship denoted by "->" can be defined as the smallest relation satisfying the below 3 criteria:
a) If an event x comes before event y and both event are part of the same process, then x happened before y (denoted by x->y).
b) If x is an event corresponding to transmission of a message by a process and b is an event corresponding to the receipt of that message by another process, then x happened before y (x->y).
c) If an event x happened before another event y (x->y) and y happened before a third event z (y->z), then x happened before z (x->z).
An event cannot happen before itself.
If an event x does not happen before event y and also the event y does not happen before x, then both the events are concurrent.

Logical clocks:
A logical clock Ci for a process Pi can be considered as a function which assigns a number Ci(x) to every event x in that process. Furthermore, the entire system of clocks can be represented by a function C in such a way that it assigns the number C(x) to any event x such that C(x) = Ci(x), where x is an event in process Pi.
This number depends on the order at which that event occurs. Therefore, if x->y then C(x) < C(y). In other words,
               1) If a process Pi has two distinct events x and y and event x occurs before event y then Ci(x) < Ci(y).
               2) If x is an event corresponding to transmission of a message by process Pi and y is an event corresponding to receipt of the message by another process Pj, then Ci(x) < Cj(y).
This logical clock can be considered to tick between the process's events. Also it is considered to tick between the transmission of a message by a process and receipt of that message by another process. We can represent this by drawing dashed tick lines in such way that there is always a tick line between two events of a process and also each message lines crosses a tick line.

Implementation of logical clocks:
For a process Pi, a logical clock can be implemented as a register Ci which contains the value Ci(x) during the event x, but changing value of Ci will not be considered as an event. To implement a logical clock, we need to make sure that the above mentioned two conditions are satisfied. This can be achieved in below way:
For condition 1): Every process Pi will increment the value of Ci between two successive events.
For condition 2): When a process Pi transmits a message at event x, the transmitted message will contain a timestamp t which will be equal to Ci(x). When the process Pj receives this message, it will increment its clock Cj to a value greater than t.
This way a system of logical clocks can be implemented to causally order events in a distributed system.


Reference: 
Leslie Lamport’s paper on time, clocks and the ordering of events in a distributed system : http://amturing.acm.org/p558-lamport.pdf