Partial order
Territory: Mechanisms
Follow causal paths without forcing independent events into a shared sequence.
On this sheet
Structure-first trail · 5 of 7
On this sheet
Structure-first trail · 5 of 7
Three stations do not make one log
A records an event and sends its observation to B. C records an event without receiving that message. B then receives A’s record. You want to combine the logs without claiming that C’s event influenced B’s receive.
Sorting by the order in which you clicked the controls would put C before the receive at B. That list is a valid record of your actions at the browser, but it supplies no communication path from C to B. The replicas have separate histories.
A partial order preserves the comparisons you can justify and leaves other pairs unordered. It lets you say that B’s receive follows A’s event while refusing to choose an order between the receive and C’s independent event. Unordered pairs are part of the answer.
Read edges as dependencies
Use three station rows. Each row contains local events in execution order. A directed edge points from a predecessor to an event that follows it. Message delivery connects observations across rows.
- Station A
- A includes
a1in messagem1for B. - Station B
b1receives m1. The graph has the edgea1 -> b1.- Station C
c1has no edge to or from either event.
The strict happens-before
relation follows three rules. Local execution orders events at one process.
Sending a message precedes receiving it. Transitivity connects a path: if x
precedes y and y precedes z, then x precedes z.
This lesson collapses the send into a copy of A’s observed history, as the
local-history sheet did. Its recorded cross-station edge is a1 -> b1.
The send remains a separate action in the ledger. The later clock lessons
give sends their own event IDs.
An edge permits causal influence; it does not prove that an application used every available value. If B receives A’s report and then calculates an unrelated checksum, the local event still follows the receive in this model. Happens-before records possible dependence through execution and communication.
Compare the connected and disconnected pairs
Use Reset lab, then the numbered reference controls.
- Reference step 1: local-event records
a1at A. - Reference step 2: send queues
m1from A to B. - Reference step 3: local-event records
c1at C. C sends no message. - Reference step 4: deliver records the receive
b1at B. - Reference step 5: compare-events compares
a1 / b1,b1 / c1, andc1 / c1.
The final control adds comparison results, not events or messages. Read its three notices in Lesson controls; the comparison strip displays only the last selected pair.
Before pressing step 5, predict each result using the figure. You need no timestamps. Inspect Predecessors if you lose track of an edge. The initial no-JavaScript view below contains three empty histories. The table after it supplies the reference results.
Partial order 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
Replica C
- 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
A missing path is a result
After step 2, B still has no observed events. A queued message is not a
receive. Step 3 changes only C. Step 4 gives B information about a1, so
the graph can establish that a1 precedes b1.
Nothing in that delivery mentions c1. No path runs from B to C either.
The two distinct events b1 and c1 are concurrent. This is a relation
between events, not a claim about whether the stations’ CPUs ran at the
same instant.
| Pair | Result | Evidence |
|---|---|---|
a1 / b1 | before | m1 provides a path from a1 to b1. |
b1 / c1 | concurrent | No path in either direction. |
c1 / c1 | equal | Both names identify the same event. |
The comparison interface has four results: before, after, equal, and concurrent. The strict happens-before relation itself consists only of the before pairs. Adding equality gives the corresponding non-strict partial order. This distinction keeps “equal” from becoming another word for “unrelated.”
You can extend the experiment after the reference run. Choose Send from B
to C and deliver the new message. The receive at C follows b1, which
follows a1. The new receive therefore follows a1 through transitivity,
even though A sent no message directly to C.
C’s old event c1 remains concurrent with b1. Learning something later
does not rewrite what an earlier event could have observed. Use Back
to inspect the frame before the new delivery, then Forward to return.
The graph can gain a new event without changing the relation between its
existing events.
Break it: sort the buttons
The control sequence records c1 before b1. If you turn that sequence into
a causal edge, you invent a dependency from C to B. B received only A’s
message; there is no evidence for the new edge.
A total sequence can still be useful for display. Both a1, c1, b1 and
c1, a1, b1 respect the required edge a1 -> b1. So does a1, b1, c1.
The partial order permits these sequences because it does not constrain C
relative to the other events.
A sorting rule produces one permitted sequence. It cannot promote that choice into evidence that an event observed another. To check your model, look for the concrete local or message edge behind each claimed dependency. If the only reason is “its row appeared first,” keep the pair concurrent.
What a path check assumes
The lab stores an event graph and retains earlier frames. An explicit graph needs storage for events and edges; a direct reachability search can visit many of them for one comparison. The reference engine keeps an ancestor index to reuse reachability information, which trades additional memory for less repeated traversal.
The concurrency claim assumes the graph includes the relevant local events and communication. Two production logs with no visible connecting message may only show incomplete instrumentation. Absence of a path in incomplete logs is not proof that no path existed in the execution.
This experiment controls the whole simulated event graph, but its replicas still have local observations. The tool’s ability to compare records from three stations must not become an algorithm in which each station can inspect everyone else’s memory.
A partition prevents delivery on a link; it does not stop local events or prove all events across that link are concurrent. A later event can still follow information received before the partition. Check ancestry rather than using connection status as a substitute.
Field notes
For a finite acyclic graph, a simple comparison uses reachability.
reachable(x, y) searches forward along local and message edges. An event’s
identity check comes first.
compare(x, y):
if x.id == y.id:
return equal
if reachable(x, y):
return before
if reachable(y, x):
return after
return concurrent
reachable(x, y):
pending = [x]
visited = {}
while pending is not empty:
event = pending.pop()
if event == y: return true
if event not in visited:
visited.add(event)
pending.extend(successors(event))
return falseLamport’s Time, Clocks, and the Ordering of Events in a Distributed System defines happens-before and shows how to extend it to a total order. The paper distinguishes causal order from a chosen ordering of concurrent events. The lab makes that distinction inspectable before adding a clock.
Read Local history if the difference between execution and observation is unclear. Continue to Lamport clocks to assign compact scalar timestamps while retaining the limits of what those timestamps can establish.