Lamport Timestamp

Distributed machines do not share a clock, and their physical clocks drift apart by milliseconds even with NTP running. So you cannot reliably say which of two events on two different servers happened first by comparing wall-clock times. Leslie Lamport solved this in his 1978 paper by giving each process a plain integer counter instead of a clock that tracks real time.

The counter is a logical clock. It does not measure seconds. It only measures order. The whole point is to capture the happened-before relation: if one event could have caused another, the cause must get the smaller number.

Formally, write A then B as A arrow B if they happen on the same process in that sequence, or if A is the send of a message and B is its receipt. Lamport timestamps guarantee that A arrow B implies timestamp of A is less than timestamp of B. The reverse is not true, and that limitation matters when you use them.

Each process holds one integer, usually starting at 0. Three rules drive every update.

First, before a process performs a local event, it increments its counter by 1. Second, when it sends a message, it increments its counter and stamps that value onto the message. Third, when it receives a message carrying timestamp T, it sets its counter to max of its own counter and T, then adds 1. That max step is what keeps a slow receiver from issuing a timestamp smaller than the sender it just heard from.

To get a total order with no ties, you break equal timestamps by a fixed tiebreaker such as the process id. So the full comparison is the pair of counter then process id. That turns a partial order into a total order, which is what algorithms like Lamport's original mutual exclusion need.

Reach for Lamport timestamps when you need a cheap, total ordering of events and you do not need to detect whether two events were truly concurrent. They cost one integer per process and one integer per message, which is close to free. They power things like ordering log entries, sequencing requests in a replicated state machine, and the classic distributed lock.

The trade-off is the one-way guarantee. If timestamp of A is less than timestamp of B, you cannot conclude A happened before B. A and B might be concurrent events that never influenced each other. Lamport clocks cannot tell causality apart from coincidence.

When you need to know that two writes were genuinely concurrent, for example to detect a conflict in a shopping cart or a key-value store, you need a vector clock instead. A vector clock keeps one counter per process, so it costs O of N space but can answer the concurrency question that a single Lamport integer cannot. Many real systems pick Lamport timestamps precisely because the vector clock cost grows with cluster size.

Picture three servers P1, P2, P3, all starting at 0. P1 does a local event and goes to 1. P1 sends a message to P3 stamped 2 (increment then send). Meanwhile P2 does two local events and reaches 2 on its own.

P3 has been idle at 0. It receives P1's message stamped 2, so it sets its counter to max of 0 and 2 which is 2, then adds 1 to get 3. Now if P3 emits any event, it is guaranteed a number above 2, so it can never appear to precede the P1 send that it just observed.

Notice P2 reached 2 entirely on its own with no contact with P1. P2's event at 2 and P1's send at 2 are concurrent, and the equal timestamps reflect that the clock cannot order them. The system resolves the tie by process id only because it needs a deterministic total order, not because one truly came first.