Reading diagrams / Topic 41 of 42
The causal trace: which order every schedule keeps
The rule
Some programs are several nodes passing messages. Here a database, db, holds a counter, and two requests, app1 and app2, each try to add one to it. Nothing fixes the order in which messages arrive, so a checker runs the model under every delivery order it allows, each a schedule, and checks each obligation in every one. The checker's source, under “Exact evidence and authored provenance”, defines the final obligation both-counted: once messages stop, the counter reads 2.
Under “Checked claim”, the verdict line gives the result over every explored schedule. In the blind write model it reads “both-counted · final · violated · 20 explored schedules · complete: true”. Complete means the exploration was not cut short: those 20 are every schedule the model allows, and a model whose exploration was cut short can never be said to hold. When an obligation fails, the view draws one schedule that breaks it, a witness. Choose “Lost update · repair” in the Model menu and the verdict holds, so there is no witness to draw.
In the witness, each node is a lane and each row a delivery step, numbered from the top. A circle is an activation: a node handling one delivered message. An arrow runs from the activation that sent a message to the one that received it, labelled with the step and the message, as in “→5 Put(1)”. An arrow from a lane's “start” was sent before any delivery.
Only a chain of arrows fixes an order. A message cannot arrive before the step that sent it, so when arrows lead from one step to another, no schedule can run the later one first. Two steps with no chain between them came in this order in this schedule only. A grey dashed line shows the order one node happened to handle two messages: that too is this schedule's order, not every schedule's, and a path that passes through one fixes nothing.
To compare two steps, select one, then choose the other under “Compare selected event with”; the inspector names the path between them. The note under “Recorded predecessor sets” sets the limit: “Paths describe one witness; they do not prove universal order, root cause or commutativity.” A chain of arrows is the one exception to universal order, since no schedule can deliver a message before sending it. The node names are the checker's. The captions under them, such as “Request A”, the reading guide and the choice of opening view are agent-authored and marked so.
- A chain of arrows from one step to another confirms it had to come first; a chain the other way rules it out.
- No chain, or only a grey local order: the trace can't tell what another schedule does.
- The verdict covers every explored schedule; why the witness fails, and how long a step took, the trace can't tell.
A lost update: a database and two requests that each add one to a shared counter. The Model menu holds the blind write and its repair.
How to read this: what each mark in these pictures means
Loading the worked examples and practice.