Local history

Territory: Mechanisms

Separate the events at a replica from the history it learns through messages.

7 min read Lab available Structure-first trail · 4 of 7

No supporting sheet required

On this sheet

Structure-first trail · 4 of 7

On this sheet

Structure-first trail · 4 of 7

A delayed message can contain old news

Station A records a draft signal report and sends its record to B. While the network delays delivery, A publishes the report. B then receives the message. Does B know that A published?

The message contains the record that A sent. It does not acquire A’s later changes before delivery. B can learn about the draft without learning about publication. A successful delivery therefore proves less than “B is up to date.” You need to identify the information in that particular message.

This distinction applies to a replicated document, a cached record, or an asynchronous notification. A sender can change after sending. A receiver can act on an earlier state even when the connection works and no message is lost. The question is which events the receiver has observed.

We’ll keep two records at each station: its local history and its observed events. The lab places both stations on one page so you can compare them. Neither station can read the other panel.

Keep execution and observation separate

A local history lists events executed at one replica. In this experiment, a1 is A’s draft event and a2 is A’s publish event. A executes them in that order. B’s receive event is b1; B does not execute a1 when it receives information about it.

An observation includes information learned from messages as well as local events. After delivery, B’s local history contains b1, while its observed events contain a1 and b1. Keeping these fields separate prevents a remote event from looking like local work.

Station A: a1: draft, send m1, then a2: publish
Message m1 from A to B: Send-time observation: a1
Station B: Receive as b1; observe a1, b1

A’s later event a2 is outside m1. Reading the rows together does not give either station the other station’s record.

Use this record through the experiment. A local event adds information at its own station. Sending copies known history into a message. Delivery makes that copy available at the receiver and records a receive event there.

For this lesson, sending does not create a separate local event. The lab records the send in its action ledger, but A’s local history still contains only a1 at that point. This keeps the first example small. The clock sheets count sends as events because a send must receive a timestamp in those models. Do not equate the ledger’s frame number with an event counter.

Hold the message while A changes

Start with Reset lab if you have used other controls. The numbered reference controls supply the event IDs used in the article.

Choose Reference step 1: local-event. A records a1 with value draft.
Choose Reference step 2: send. Inspect m1 in Queued messages. Its observed history contains a1.
Choose Reference step 3: local-event. A records a2 with value publish. Inspect m1 again before delivery.
Choose Reference step 4: deliver. B records b1. Compare Local history and Observed events at each station.

Use the numbered control for the receive too: it supplies the name b1. The ordinary Deliver m1 from A to B control performs delivery with a generated event ID, so its record has a different name.

Back and Forward select recorded frames without changing their state. Return to the latest frame before issuing another action. Play visits existing frames; it does not send or deliver anything. With reduced motion, Next recorded frame advances once per press.

Without JavaScript, the initial panels below show empty histories and an empty queue. The figure above and the staged records below describe the complete run without requiring the controls.

Local history lab

Replica A

Visible value: No local values
Local history: No local events
Observed events: No events observed
Predecessors: No predecessors

No events observed

Replica B

Visible value: No local values
Local history: No local events
Observed events: No events observed
Predecessors: No predecessors

No events observed

Queued messages

No queued messages

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

Account for the missing event

Before the send, A has observed a1; B has observed nothing. Sending changes the queue, not B’s knowledge. There is now a copy of A’s observation in m1, but B cannot use it until delivery.

After A publishes, A’s history is a1, a2. The message still contains only a1. A send-time copy is part of the model: later changes to the sender do not mutate an existing message.

After delivery, B knows a1, b1. Its receive has a1 as a predecessor. A’s publish also has a1 as a predecessor. Both events follow the draft, but neither follows the other through a message or local history.

After reference step 4
Station	Local history	Observed events
A	`a1, a2`	`a1, a2`
B	`b1`	`a1, b1`

The queue is empty, but B has not observed a2 and A has not observed b1. Draining this queue does not make the histories equal.

The final comparison calls a2 and b1 concurrent. Here that means there is no causal path between them. It does not require simultaneous execution. You clicked publish before receive, but that order exists in the experiment’s controls, not as communication between A and B.

To give B information about a2, choose Send from A to B after the reference run, then deliver the new message. B now learns that event. This also creates another receive at B. It does not rewrite b1 to pretend that the first delivery contained more information.

Break it: read the sender at delivery

Suppose delivery reads A’s current history instead of the message’s saved payload. Step 4 would give B both a1 and a2. The displayed result might look convenient, but no message sent after a2 exists.

That incorrect model replaces a delayed message with a remote read. It hides stale data and can make B appear to depend on an event it could not have observed. A test that checks only whether the queue becomes empty would miss the error.

Check the payload at step 2 and step 3. It must remain a1 even as A changes. Then check B after step 4. The absence of a2 is the expected result, not a delivery failure. This test distinguishes message delivery from consulting a shared object that both replicas can read.

The cost of an explicit history

The lab retains event IDs, predecessor relationships, and observed-event sets. Its messages copy known history. Storage and message size can grow with the number of events, even if an application only displays the latest report. This representation makes evidence visible; it is not a compact replication protocol.

The model assumes each station executes a sequence of local events and that event IDs are unique. A real process with internal concurrency needs a more precise definition of its local ordering. Reusing an event ID after a restart would make two events indistinguishable in this graph.

You control delivery. Sending does not guarantee receipt, and healing a partition only permits delivery of pending messages. An empty queue here means there are no queued copies in this simulation. It does not prove that no external sender has an update or that all replicas have equal state.

The full-page trace belongs to the teaching tool. A deployment would need instrumentation and a collection protocol to assemble comparable records. Even collected logs do not automatically establish an order between events that exchanged no information.

Field notes

This pseudocode describes the history lesson. Each replica starts with an empty history sequence and observed set. fresh_id never reuses an event name. A predecessor edge states what the new event follows.

local(value):
  event = fresh_id()
  predecessors[event] = last(history), if present
  history.append(event)
  observed.add(event)

send(peer):
  queue(peer, copy(observed))

receive(message):
  event = fresh_id()
  predecessors[event] =
    message.observed union {last(history), if present}
  history.append(event)
  observed = observed union message.observed union {event}

The receive belongs to the receiver’s local history. Its remote predecessors come from the message. The sender does not learn that the receive occurred merely because the tool shows it; that would require communication back to the sender.

Leslie Lamport’s Time, Clocks, and the Ordering of Events in a Distributed System defines ordering through process events and message transmission. The lab’s explicit observed sets are a teaching representation of those dependencies, not a claim that Lamport requires every message to include an entire history.

The next sheet, Partial order, turns these predecessor paths into a comparison rule. Keep a2 and b1 in mind: sharing a predecessor did not put either event after the other.