Lamport Timestamps

Summary: A method for generating a total ordering of events in a distributed system that is consistent with causality.

Sources: chapter9

Last updated: 2026-04-17

Proposed by Leslie Lamport in 1978, Lamport timestamps provide a way to generate a total order of events in a distributed system (source: chapter9, p. 345).

How it Works

Each node keeps a counter of the number of operations it has processed. A Lamport timestamp is a pair of (counter, node_id) (source: chapter9, p. 345).

Two timestamps are compared by looking at the counter first, and then the node_id as a tie-breaker (source: chapter9, p. 346).
This makes every timestamp unique and provides a total order (source: chapter9, p. 346).

Maintaining Causality

To ensure the ordering is consistent with causality, the following rule is used:

Every node and every client keeps track of the maximum counter value it has seen so far (source: chapter9, p. 346).
When a node receives a request or response with a maximum counter value greater than its own, it immediately increases its own counter to that value (source: chapter9, p. 346).

Limitations

While Lamport timestamps provide a total order, that order only emerges after all operations have been collected (source: chapter9, p. 347).

A node cannot decide right now whether a request (e.g., to create a unique username) should succeed or fail because it doesn’t know if another node is concurrently processing a request with a lower timestamp (source: chapter9, p. 347).
To solve this problem, you need to know when the total order is finalized, which leads to the concept of total-order-broadcast (source: chapter9, p. 348).