Lamport timestamp

Introduction

Lamport timestamp is a method proposed by Leslie Lamport for generating sequence numbers that are consistent with a causality law.

Lamport timestamp

1. Each node (replica) is assigned a unique ID.
2. (counter, NodeID) is the timestamp
3. If the counters have the same value, the one with the larger node ID is considered the larger timestamp. (3,2) < (3,5)
4. When a node generates a timestamp, it compares the largest value it is aware of with the client's value and sets the larger value as the timestamp counter value.

The figure below shows a concrete example of a Lamport timestamp.

The order of execution in the above diagram is as follows.

(1,1)<(1,2)<(2,1)<(2,2)<(3,1)<(4,1)<(5,1)<(5,2)

Comparing this sequence with the figure shows that real time and the time line do not match. For example, in real time, (3,1) < (2,2) and (5,2) < (5,1), but in reverse order in the Lamport timestamps.

Why is this so?

That is because the Lamport timestamp is always intended to define the entire sequence. In other words, Lamport timestamp cannot identify whether two operations were performed in parallel or causally dependent. Because of this, it is designed to be more compact than the version vector.