Offline-first and sync

What is a Lamport timestamp?

A Lamport timestamp is a counter that each process keeps and attaches to the messages it sends. The process increments it between events and, on receiving a message, moves it past the timestamp the message carried, so if one event could have caused another, the cause always has the smaller number.

TL;DR

Two rules, increment between events and carry the counter on messages, let Lamport timestamps respect cause and effect, and breaking ties by process identifier gives a total order every device can compute. A smaller timestamp does not prove one event came first, so spotting concurrent changes needs a vector clock. Lamport timestamps also say nothing about elapsed time.

Learning objectives

After reading this article you will be able to:

  • Explain the happened-before relation and why device clocks are not enough
  • Describe the two rules that keep Lamport timestamps consistent with causality
  • Recognise what Lamport timestamps cannot tell you about concurrency and elapsed time

Device clock limits for event ordering

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. The obvious way to order events across devices is to stamp each one with the time, and Leslie Lamport’s 1978 paper starts by explaining why that is not reliable.

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 timestamp rules

Lamport timestamps follow two rules: increment the counter between events, and carry it on messages. Lamport gave each process a clock that is just a counter, with no connection to physical time, and for the counters to respect “happened before”, these 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.

Lamport timestamp tie-breaking and total order

Lamport broke ties between equal timestamps with any fixed ordering of the processes. Compare the counters first; if they are equal, compare the process identifiers. This is needed because two concurrent events can end up with the same counter value.

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.

Lamport timestamps in modern sync software

The counter plus identifier pattern is common in sync software, including Automerge, Yjs, and hybrid logical clocks:

  • 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 timestamp limitations

Lamport timestamps cannot detect concurrency or see outside the system, 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.

Frequently asked questions

Is a Lamport timestamp the same as a vector clock?

No. A Lamport timestamp is a single number, so it can order events but cannot show whether two events were concurrent. A vector clock keeps one counter per process, which is enough to tell the two cases apart.

Do Lamport timestamps need the devices' clocks to agree?

No. They are counters, not times of day, and can be implemented without any timing mechanism. That is why they suit devices that have been offline and may have drifted.

What does happened before mean in distributed systems?

Lamport defined order by what could have influenced what. Earlier events in the same process, and sending a message compared with receiving it, are ordered, and so is anything linked through a chain of those. Two events where neither happened before the other are concurrent.

How does Automerge order concurrent writes?

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.

What is a hybrid logical clock?

It combines a logical counter with physical time. Its authors designed it to capture causality like a logical clock while staying close to the NTP clock, so it can stand in where physical timestamps are expected.

Can a Lamport timestamp tell how old a message is?

No. Logical clocks order events but cannot tell you whether a message is seconds old or days old, so expiry and freshness checks still depend on a wall clock and its errors.

Sources

Build it with Offline Protocol

Offline Protocol's replicated documents merge deterministically, with a fixed rule for each collection type, so every device reaches the same result whatever order changes arrive in. The shared state guide lists the rules and how to test them.

Read the shared state guide