Lamport Timestamps

Imagine a group of friends telling a continuous story via text messages. Because cell networks are weird, messages might arrive out of order. To keep track of the story, everyone agrees to add a number to the end of their text.

If Alice sends a text ending in 1, Bob sees it and sends his reply ending in 2. If Charlie was offline and wants to jump in, he looks at the highest number he has seen (2) and sends his message ending in 3.

This simple numbering game is exactly how Lamport Timestamps work in distributed systems.

The Core Concept

Invented by Leslie Lamport, a Lamport Timestamp is a simple algorithm to implement a Logical Clock. It provides a way to assign a sequence number to every event in a distributed system so we can definitively order them, without relying on physical, drifting hardware clocks.

It uses a simple integer counter on every server.

The Algorithm: How It Works

It’s surprisingly elegant and consists of just a few rules:

1. Initial State: Every server (process) starts with a local counter set to 0.
2. Local Events: Every time a server performs a local action (like writing to a database), it increments its own counter by 1. (counter = counter + 1)
3. Sending Messages: When a server sends a message over the network to another server, it "piggybacks" its current counter value onto the message.
4. Receiving Messages: When a server receives a message, it looks at the timestamp attached to the message. It updates its own local counter to be greater than both its current value and the received value.
   • counter = MAX(local_counter, received_counter) + 1

Why This is Brilliant

Let's say Server A is running fast and is at counter 10. Server B has been idle and is at counter 2. Server A sends a message (timestamp 10) to Server B. When B receives it, B realizes it has fallen behind causally. Rule 4 kicks in: B updates its clock to MAX(2, 10) + 1 = 11.

Now, any subsequent action on Server B will have a timestamp of 12 or higher. This guarantees that Server B's response will always have a higher timestamp than Server A's initial message. The "happens-before" relationship is perfectly preserved!

The Catch: Total vs. Partial Ordering

Lamport timestamps give us a Total Order. If you look at any two events across the entire system, you can always say which one has the smaller timestamp (if there's a tie, you break it by looking at the Server ID).

[!WARNING] But there is a fatal flaw. If Event A causes Event B, A's timestamp will definitely be smaller than B's. BUT, just because Timestamp X is smaller than Timestamp Y, it does not mean X caused Y. They could be completely unrelated events happening concurrently on opposite sides of the world.

Lamport timestamps can't distinguish between events that causally affected each other and events that just randomly happened concurrently.

To solve this specific flaw, system designers had to invent a slightly more complex tool: Vector Clocks.

Summary

• Lamport Timestamps use a simple integer counter on each node to order events without physical clocks.
• Nodes increment counters locally and piggyback them on network messages.
• Receiving nodes update their counters to be higher than any incoming message.
• It guarantees that causal events are ordered correctly.
• It cannot identify if two events were concurrent (unrelated).