What is a Lamport timestamp?

The obvious way to order events across devices is to stamp each one with the time. Leslie Lamport’s 1978 paper starts by explaining why that is not reliable. Physical clocks are not perfectly accurate, so a specification written in terms of real time is only as good as the clocks the system contains.

Lamport instead defined order by what could have influenced what. He called this relation “happened before”:

• If two events happen in the same process, the earlier one happened before the later one.
• Sending a message happened before receiving it.
• If a happened before b, and b happened before c, then a happened before c.

Two events where neither happened before the other are concurrent. Neither could have affected the other, whatever the clocks say. “Happened before” is therefore only a partial order: for some pairs of events, there is no answer to which came first.

Lamport then gave each process a clock that is just a counter, with no connection to physical time. For the counters to respect “happened before”, two implementation rules are enough:

1. Increment between events. Each process increases its counter between any two of its own events.
2. Carry it on messages. Every message carries the sender’s counter. When a process receives a message, it sets its own counter to at least its current value and greater than the timestamp on the message.

Together these guarantee what Lamport called the Clock Condition: if event a happened before event b, then a’s timestamp is smaller than b’s. A reply can never carry a smaller number than the message it answers, and a change made after seeing another change always has a larger number than that change.

Two concurrent events can end up with the same counter value. To order every event, Lamport broke ties with any fixed ordering of the processes. Compare the counters first; if they are equal, compare the process identifiers.

The result is a total order that every participant can compute on its own and that never contradicts “happened before”. Lamport notes it is not unique. Different valid clocks give different total orders, and only the partial order is fixed by what actually happened.

In his commentary on the paper, Lamport says the paper is really about how a total order of requests lets a network of processors run any system described as a state machine. The paper illustrated it with distributed mutual exclusion.

The counter plus identifier pattern is common in sync software:

• Automerge gives every operation an ID made of a counter and the actor ID that generated it. When two people set the same property at once, it orders their writes by counter first and uses the actor ID only to break ties, which decides the last writer wins value.
• Yjs uses Lamport timestamps to identify each change and to track the order in which each client created them. Each change has an ID made of a client number and a clock.
• Hybrid logical clocks combine a logical counter with physical time. Their authors designed them to capture causality like a logical clock while staying close to the NTP clock, so they can stand in where physical timestamps are expected.

Lamport timestamps have two limits that matter in practice.

They do not detect concurrency. The Clock Condition only works one way. Lamport points out that the converse cannot hold: a smaller timestamp does not mean an event happened before another. To tell whether two changes were concurrent, which is what a sync engine needs to spot a conflict, you need a vector clock.

They cannot see outside the system. Lamport describes a person who makes a request on one computer, then phones a friend in another city, who makes a second request on a different computer. The second request can receive a lower timestamp and be ordered first, because the phone call never passed through the system. Lamport’s fixes were either to carry the earlier timestamp across by hand or to use synchronised physical clocks.

A related point is that logical clocks say nothing about elapsed time. They order events but cannot tell you whether a message is seconds old or days old. Checks that need real age, such as expiry or freshness, still depend on a wall clock and its errors. Offline Protocol’s security documentation lists this as a residual risk: freshness checks depend on the verifier’s clock, and a wrong clock can reject legitimate control frames.