Trusted answers to developer questions

Adnan Abbas

**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.

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.

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`

.

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, the final clock value is 3.

RELATED TAGS

communitycreator

CONTRIBUTOR

Adnan Abbas

RELATED COURSES

View all Courses

Keep Exploring

Related Courses