Leslie Lamport proposed this scheme to provide ordering of events in a

distributed environment using

logical clocks. Because it is impossible to have perfectly synchronized clocks and

global time in a distributed system, it is often necessary to use logical clocks instead.

**Definitions:**

Happened Before Relation (->). This relation captures causal dependencies between events, that is, whether or not events have a cause and effect relation. This relation (->) is defined as follows:

- a -> b, if a and b are in the same process and a occurred before b.
- a -> b, if a is the event of sending a message and b is the receipt of that message by another process.
- If a -> b and b -> c, then a -> c - that is, the relation has the property of transitivity.

Causally Related Events: If event a -> event b, then a causally affects b.

Concurrent Events: Two distinct events a and b are concurrent (a || b) if (not) a -> b and (not) b -> a. That is, the events have no causal relationship. This is equivalent to b || a.

For any two events a and b in a system, only one of the following is true: a -> b, b -> a, or a || b.

Lamport introduced a system of logical clocks in order to make the -> relation possible. It works like this: Each process P_{i} in the system has its own clock C_{i}. C_{i} can be looked at as a function that assigns a number, C_{i}(a) to an event a. This is the timestamp of the event a in process P_{i}. These numbers are not in any way related to physical time -- that is why they are called logical clocks. These are generally implemented using counters, which increase each time an event occurs. Generally, an event's timestamp is the value of the clock at that time it occurs.

**Conditions Satisfied by the Logical Clock system:**

For any events a and b, if a -> b, then C(a) < C(b). This is true if two conditions are met:

- If a occurs before b, then C
_{i}(a) < C_{i}(b).
- If a is a message sent from P
_{i} and b is the recept of that same message in P_{j}, then C_{i}(a) < C_{j}(b).

**Implementation Rules Required**

- Clock C
_{i} is incremented for each event: `C`_{i} := C_{i} + d (d > 0)

- if a is the event of sending a message from one process to another, then the receiver sets its clock to the max of its current clock and the sender's clock - that is,
` C`_{j} := max(C_{j}, t_{m} + d) (d > 0)

.

.