What are Lamport clocks?

Lamport clocks represent time logically in a distributed system. They are also known as logical clocks. The idea behind Lamport clocks is to disregard physical time and capture just a “happens-before” relationship between a pair of events.

Why use Lamport clocks?

Time synchronization is a key problem in distributed systems. Time is used to order events across servers. Using physical clocks to order events is challenging because real synchronization is impossible and clocks experience skew. A clock skew is when different clocks run at different rates, so we cannot assume that time t on node a happened before time t + 1 on node b.

Instead of employing physical time, Leslie Lamport proposed logical clocks that capture events’ orderings through a “happens-before” relationship.

Defining the happens-before relation

An event is something happening at a server node (sending or receiving messages, or a local execution step). If an event a happens before b, we write it as a -> b.

There are three conditions in which we can say an event a happens before b:

• If it is the same node and a occurs before b, then a -> b
• If c is a message receipt of b, then b -> c
• Transitivity: If a -> b and b -> c, then a -> c

The following diagram illustrates the happens-before relation:

A happens-before relation does not order all events. For instance, the events a and d are not related by ->. Hence, they are concurrent. Such events are written as a || d.

Implementing Lamport clocks

Lamport clocks tag events in a distributed system and order them accordingly. We seek a clock time C(a) for every event a. The clock condition is defined as follows:

If a -> b, then C(a) < C(b).

Each process maintains an event counter. This event counter is the local Lamport clock.

The Lamport clock algorithm works in the following way:

• Before the execution of an event, the local clock is updated. This can be explained by the equation C_i = C_i+1, where i is the process identifier.
• When a message is sent to another process, the message contains the process’ local clock, C_m.
• When a process receives a message m, it sets its local clock to 1+max(C_I, C_m).

The following diagram illustrates how the Lamport clock algorithm works:

In the example above, all local clocks start from a value of 0. Before the execution of an event, the local clock increments by 1. Notice that P2’s clock starts from 0, but on the arrival of the message m1 from P1, it updates its clock in accordance with the third rule mentioned above, i.e., 1+max(C_i, C_m) where C_i = 0 and C_m = 2.

Hence, P2’s final clock value is 3.

Note: d is an event on P3, so, C(d) = 1, where d is parallel to a.