Lamport clocks

Order causal predecessors with one counter without mistaking scalar order for causality.

5 min read Lab available Structure-first trail · 6 of 7

On this sheet

Structure-first trail · 6 of 7

On this sheet

Structure-first trail · 6 of 7

Put the send before the receive

Two stations record events without a shared physical clock. You want to sort their records so that a message receive never appears before its send. Copying every predecessor into each record would work as evidence, but you want a smaller timestamp for ordering.

A Lamport clock gives each station one counter. Local events increase it. Messages include the sender’s counter, and a receive moves the receiver past that value. The rule preserves the direction of causal paths: if x happens before y, then L(x) < L(y).

The reverse statement does not hold. A smaller timestamp can belong to an independent event. We’ll keep the predecessor graph next to the scalar readings so that you can see both facts in the same run.

One counter advances at each event

Start each counter at zero. Before a local event or send, increment the local counter and use the new value as the event’s timestamp. A send includes that timestamp in its message.

At a receive, take the maximum of the local counter and the message timestamp, then add one. Taking the maximum alone would permit the receive to have the same timestamp as its send. The extra increment makes the ordering strict.

Station A: a1@1, then send a2@2
Message m1: Timestamp 2, saved at send time
Station B: b1@1, then receive b2@3

Local paths connect a1 to a2 and b1 to b2. The message connects a2 to b2. No path connects b1 to a2, despite their different timestamps.

Read a2@2 as event a2 with scalar timestamp 2. The number measures logical progress under these update rules. It is not a duration or a wall-clock reading. B can jump from 1 to 3 in one receive; there need not be a local B event with timestamp 2.

Unlike the first two sheets, this lesson counts a send as a local event. A’s second event is the send a2. Its message retains timestamp 2 even if you later create another event at A.

Record equal and unequal concurrent timestamps

Reset the lab and use the numbered controls. They reproduce the IDs in the figure and keep the comparison independent of generated event names.

Reference step 1: local-event creates a1 at A with timestamp 1.
Reference step 2: local-event creates b1 at B with timestamp 1. Neither station has sent a message yet.
Reference step 3: send creates a2 at A with timestamp 2 and queues m1 for B.
Reference step 4: deliver creates b2 at B with timestamp 3.

At step 2, predict whether matching clock readings imply matching knowledge. At step 3, ask whether B’s timestamp 1 proves that b1 caused a2. After delivery, inspect Predecessors, Event comparison, and the Total display order notice rather than reading only the large clock values.

Back and Forward revisit recorded frames. The lab stores those frames; it does not rerun actions when you select them. The static view below starts both clocks at zero, with no events or queued messages. The next section provides the complete trace for readers without JavaScript.

Lamport clock lab

Replica A

Visible value: No local values
Scalar clock: 0
Local history: No local events
Predecessors: No predecessors

No events observed

Replica B

Visible value: No local values
Scalar clock: 0
Local history: No local events
Predecessors: No predecessors

No events observed

Queued messages

No queued messages

Total display order (timestamp, replica ID): No events. Tie breaking is not causality. A lower timestamp does not prove happens-before.

Each replica starts with an empty local history. No messages have been delivered.

Invariant checks

Local history is ordered: yes
Observed events have causal paths: yes
Local clock increases: yes
Causal predecessors have lower timestamps: yes

Separate the clock condition from its converse

After the two local events, A and B each show 1. There is no causal path between a1 and b1. Distinct events with equal Lamport timestamps cannot precede one another under the clock condition.

A then sends. It advances to 2, but B’s earlier local event still has no path to A. The pair b1@1 and a2@2 is concurrent even though 1 is less than 2. This pair is the counterexample to inferring happens-before from a scalar comparison.

On delivery, B computes max(1, 2) + 1 = 3. Its receive follows both the local predecessor b1 and the send a2. Through a2, it also follows a1. The timestamp exceeds each predecessor’s timestamp, as required.

Event	Timestamp	Direct predecessors
`a1`	1	none
`b1`	1	none
`a2`	2	a1
`b2`	3	b1, a2

The clock condition holds on every path. The empty predecessor entry for b1 does not change when the browser later records a2.

The lab’s Event comparison uses graph paths, not scalar values. At the end it selects the unequal concurrent pair b1 / a2. This is why the panel can report concurrency that the scalar fields alone cannot establish.

The total display order sorts by (timestamp, replica ID). In this run it is a1@1/A, b1@1/B, a2@2/A, b2@3/B. The replica-ID rule puts A before B when their timestamps tie. It creates a deterministic display order while preserving the causal edges.

That order does not make a1 a predecessor of b1. A different agreed replica ordering could reverse the tied pair without violating any causal constraint. A total order chooses a position for every distinct pair; the causal partial order leaves some pairs incomparable.

Break it: smaller means observed

Suppose you keep only scalar timestamps and implement observed(x, y) = L(x) < L(y). At step 3 it reports that a2 observed b1, since 1 is less than 2. Yet A has received no message from B.

The same test would give the right answer for a1 and a2, which makes the bug easy to miss with only local test cases. You need the independent B event to show that the counter compresses away a distinction.

Tie breaking cannot repair the lost information. It orders equal timestamps, but the false inference already occurs with unequal timestamps. Keep the one-way implication: happens-before requires an increasing clock; an increasing clock does not prove happens-before.

A rule that selects the largest timestamp as a winning value is an application conflict policy. It does not recover which versions a writer observed. If your application must preserve concurrent values, discarding all but the largest scalar timestamp discards necessary information.

One counter with limited evidence

Each process and message needs one scalar clock rather than a component for each process. Updating it requires an increment and, at receive, a maximum. That is constant-size metadata in counter entries, though representing an unbounded count still requires more bits as it increases.

Counters must not wrap or move backward while their identity remains in use. A restart needs durable clock state or an identity policy that prevents confusing a new execution with an old one. This short run does not exercise counter exhaustion.

The rule assumes local events have an order and messages retain send-time timestamps. It does not require synchronized physical clocks or FIFO delivery. A duplicate delivery creates a new receive event and advances the receiver again; it does not change the original send’s timestamp.

Sorting known records is also different from delivering an irrevocable total sequence online. A station may receive a lower timestamp later. It needs additional protocol rules to know when a prefix is safe to deliver or commit. Lamport timestamps alone do not provide consensus, reliable delivery, or knowledge that no message remains in transit.

Field notes

The clock starts at zero. Record the updated value on the event, not a reference to a mutable counter. The last function sorts records already available to the caller.

local_event():
  clock = clock + 1
  record_event(clock)

send(peer):
  clock = clock + 1
  record_send(clock)
  queue(peer, timestamp = clock)

receive(message):
  clock = max(clock, message.timestamp) + 1
  record_receive(clock)

display_order(events):
  return sort(events, by = (timestamp, replica_id))

Leslie Lamport’s Time, Clocks, and the Ordering of Events in a Distributed System states the clock condition, gives logical-clock implementation rules, and constructs a total order using a process ordering to break ties. The paper’s distributed algorithms add communication rules beyond the clock update.

Partial order explains the graph evidence used beside these counters. Vector clocks keeps separate components so a comparison can distinguish the two concurrent histories that a scalar order puts in one sequence.