Lamport Timestamps

The Clock is an important building block in cloud computing systems and distributed systems. Clock is important to maintain the order of events across different processes. Lamport timestamp algorithm is one of the simplest algorithms that is used to maintain the order of events in a distributed system. Lamport’s algorithm or the logical clock algorithm was proposed by Leslie Lamport in the 1970s and still, almost all distributed systems use some form of logical ordering which can be either Lamport’s or some variation of Lamport’s algorithm.

Lamport clock basically provides a partial order of events that is specified using the “happened before” relationship. A happened-before relationship is defined using the symbol “->” and implies that if an event A causally happens before another event B, then timestamp(A) < timestamp(B). The term Causality here means that if one event leads to another, then there is a path of events from the first event to the second event. The algorithm provides only partial order of events as we cannot relate all the events with the “happened before” relationship.

In a distributed system, we can define mainly 3 types of events that each process can execute.

1. A local event (An instruction being executed)
2. A send event
3. A receive event

Based on these, we can define the basic rules as follows:

• For a local event, a → b, if time(a) < time(b)
• If process P1 sends a message to process p2, then, send(message) → receive(message)
• If a → b and b → c then a → c

The events update the logical timestamp according to the below rules:

1. Before executing an event, the process increments the logical timestamp by 1.

Logical_timestamp = Logical_timestamp + 1

2. During a send event, the process increments the logical timestamp by 1 and sends the time along with the message.

Logical_timestamp = Logical_timestamp + 1

3. During a receive event, the counter of the recipient is updated to the max value of its own Logical_timestamp and the timestamp in the received message. It then increments the timestamp by 1.

Logical_timestamp = max(Logical_timestamp, time_received) + 1

Fig 1: Lamport's Timestamp

The above picture has depicted the timestamp for each event in 3 different processes. Each event is marked with a name along with the timestamp to improve the readability.

Here, we could say that E ->B as timestamp(E) < timestamp(B), and there is a causal path from A to B. Similarly, C->I, F->G and so on. But if we consider the events, A and E we have a timestamp(A) = timestamp(E). But there is no causal path from A to E or E to A. Similarly, for the events, A and G, we have timestamp(A) < timestamp(G). But there is no causal path from A to G or G to A. These events, are called concurrent events and pair of concurrent events doesn’t have a causal path from one event to another. Lamport timestamps are not guaranteed to be ordered or unequal for concurrent events. Hence, we have to keep in mind:

A -> B ⇒ timestamp(A) < timestamp (B)
timestamp(A) < timestamp (B) ⇒ {A -> B OR A and B are concurrent}

Reference:

[1]. https://www.coursera.org/learn/cloud-computing/lecture/4nPtE/2-4-lamport-timestamps