Lamport Timestamp

This post introduces the Lamport timestamp.

Here are two log lines from two different servers.

[server-a] 12:00:00.150  order created
[server-b] 12:00:00.120  order cancelled

The cancellation is 30 milliseconds ahead of the creation. So did someone cancel an order that did not exist yet?

Probably not. The two wall clocks are simply out of step with each other.

Why wall clocks cannot be trusted

Physical clocks each run at a slightly different rate. A common quartz oscillator is off by 20 to 30 ppm, and since 1 ppm works out to 86 milliseconds a day, an uncorrected clock drifts by roughly two seconds per day.

NTP does keep correcting it, of course. While the offset is small, it nudges the rate at which the clock runs and catches up gradually (slew).

The trouble starts when the offset is large. By default ntpd jumps the clock in one move (step) once an offset above 128 milliseconds persists, and if the clock had been running ahead, that jump goes backwards. An event that happened later then ends up with an earlier timestamp.

Time moving backwards breaks things more often than you would expect. The leap second inserted in 2012 famously locked up servers across a number of services. That is why clocks are now often slowed down for a while (leap smear) instead of being stepped back.

In short, a wall clock in a distributed system is fine for “roughly what time is it,” but it cannot serve as the basis for “which of these happened first.”

So can we order events without a clock at all? That is exactly what Leslie Lamport answered in his 1978 paper Time, Clocks, and the Ordering of Events in a Distributed System.

It is one of the most cited papers in computer science, and Lamport received the Turing Award in 2013 for his work on distributed systems.

The happened-before relation

Lamport starts from causality rather than from time. You may not know what time an event occurred, but you can know what could have caused what.

This is the happened-before relation, written a → b. It has only three rules.

The important part is that this relation is a partial order, not a total one.

Two events between processes that never exchanged a message cannot be ordered at all. Such events are called concurrent.

Be careful with that word. Concurrent does not mean “happened at the same time” but could not have influenced each other. Two events an hour apart are concurrent if neither knows about the other.

The algorithm

Now we attach numbers to that relation. Each process keeps one counter, and the rules fit in three lines.

1. On an internal event, increment the counter by 1.
2. When sending a message, increment the counter by 1 and attach that value to the message.
3. When receiving a message, take the larger of your counter and the received value, then add 1.

The third rule is the load-bearing one. The result is always greater than the received value, which guarantees that a send has a smaller number than its matching receive.

An example

Follow three processes exchanging messages.

Notice how P3’s counter jumps from 1 straight to 5.

P3 has only experienced one event of its own, but it has been affected by a chain that started at P1 and passed through P2. The length of that chain is what the number reflects.

In other words, this number is not a time. It is a position in a causal chain.

Implementation

Three rules, so the code is short.

class LamportClock:
    def __init__(self) -> None:
        self.counter = 0

    def local_event(self) -> int:
        self.counter += 1
        return self.counter

    def send(self) -> int:
        self.counter += 1
        return self.counter          # timestamp to attach to the message

    def receive(self, received: int) -> int:
        self.counter = max(self.counter, received) + 1
        return self.counter

The whole state is one integer, and no agreement between processes is required. That is remarkably cheap for a distributed algorithm.

What it guarantees, and what it does not

This is where the common misunderstanding lives.

A Lamport timestamp guarantees exactly one direction.

Why does the second one fail? In the example above, P2’s first event and P3’s first event both carry the value 1.

Equal values aside, what about P1’s second event (2) and P3’s first event (1)? P3’s number is smaller, yet the two events have nothing to do with each other. They are concurrent.

So a smaller number tells you only that the event may have happened before, or may be entirely unrelated.

A Lamport timestamp cannot tell you whether two events are concurrent. Causality implies ordering, but visible ordering does not imply causality. Miss that distinction and you will treat two conflicting updates as if one followed the other.

Building a total order

A partial order is not always enough. Sometimes you have to form a queue, for instance when several nodes compete for one resource.

The fix is simple. When timestamps tie, break the tie with a predetermined order such as the process ID.

def order_key(timestamp: int, process_id: str) -> tuple[int, str]:
    return (timestamp, process_id)

Every node computes this order identically. Given the same set of events, whoever does the sorting produces the same queue.

The original paper uses exactly this total order to build a distributed mutual exclusion algorithm. There is no central coordinator; every node reaches the same conclusion from the same rules.

Keep in mind that this order is agreed upon rather than real. It forces a queue onto concurrent events, so the one that actually happened first may end up behind.

Vector clocks

So how do you detect concurrency as well?

One number is not enough. You carry one counter per process instead, which is the vector clock, formalised independently by Colin Fidge and Friedemann Mattern in 1988.

The rules are nearly the same as before.

1. On an internal event, increment your own slot by 1.
2. When sending, increment your slot and attach the whole vector.
3. When receiving, take the maximum in each slot, then increment your own slot by 1.

def receive(mine: list[int], received: list[int], me: int) -> list[int]:
    merged = [max(a, b) for a, b in zip(mine, received)]
    merged[me] += 1
    return merged

Comparison is simple too. If every slot is less than or equal and at least one is strictly less, it happened before; if neither vector dominates the other, the events are concurrent.

The price of detecting concurrency is space. With N processes the vector has N slots, and every message has to carry it.

In an environment where nodes join and leave constantly, that cost becomes a real burden.

Where they are already in use

Logical clocks are still in service well outside the textbook.

• Conflict detection in distributed databases: Riak, Voldemort, and the Dynamo family use vector clocks to tell whether two updates to the same key conflict or follow one another.
• Causal consistency: keeping a reply from appearing before the post it answers requires causal order, and logical clocks provide the basis for it.
• Distributed mutual exclusion and snapshots: the applications from the original paper, still in place.
• Hybrid logical clocks (HLC): physical time and a logical counter packed into one value, readable by humans while preserving causal order. CockroachDB and MongoDB take this approach.
• Version control: Git’s commit graph is, in the end, a partial order recording the happened-before relation.

If your logs carry nothing but wall-clock times, adding a per-request logical counter or a causal ID makes debugging far easier. The ordering can be reconstructed even when server clocks disagree.

Practice problems

1. Reconstruct timestamps from a message log

Given a record of messages exchanged between three processes, compute the Lamport timestamp of every event. The LamportClock above is all you need.

2. Find the concurrent events

Apply vector clocks to the same log and print every pair of concurrent events. Comparing this with the result from the first exercise shows exactly what Lamport timestamps miss.

3. Verify the total order

Check that sorting by (timestamp, process ID) produces an identical order on every node. Shuffling the order in which events arrive must not change the result.

References

• Lamport timestamp — Wikipedia
• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (CACM, 1978)
• Happened-before — Wikipedia
• Vector clock — Wikipedia
• Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (HLC, 2014)