A valid answer can still be wrong now

A reader types apple. Search A begins. Before A finishes, the reader types apple pie. Search B begins and finishes first. The surface correctly shows results for apple pie. Then A finishes and replaces them with results for apple.

No request failed. No worker returned corrupt data. Each result is correct for the question it received. The last write is wrong because completion order is not question order.

“Cancel the first request” sounds sufficient until cancellation arrives after the response, the remote server ignores it, or a queued callback is already committed to run. Cancellation is useful. It is not a proof that old work has lost every route to publication.

Number the questions, not the callbacks

Let $g_{current}$ be a monotonically increasing natural number. Each semantic query transition advances it. Every root task, child task, partial result, terminal result, cache observation, and effect receipt carries the generation that created it.

Publication is one guarded operation:

$$\operatorname{admit}(e) \iff e.g=g_{current}.$$

An admitted event may update visible state. A rejected event can still release resources and record diagnostics, but it cannot alter the answer, selection, announcement, or pending marker belonging to the current question.

HANDLE-SETTLEMENT(EVENT, STATE)
Input:  child settlement EVENT and current STATE
Output: updated STATE plus zero or one publication effect

owned ← SETTLE-CHILD(STATE.owned, EVENT.child, EVENT.outcome)
next ← WITH-OWNED(STATE, owned)
if EVENT.generation ≠ STATE.currentGeneration
    return REJECT-STALE(next, EVENT.identity)
if not OWNS(STATE, EVENT.child)
    return REJECT-UNOWNED(next, EVENT.identity)
answer ← INCORPORATE(STATE.answer, EVENT)
return PUBLISH(WITH-ANSWER(next, answer))

The settlement update precedes the publication guard because stale work still has an owner who must learn that it ended. The event cannot borrow the current generation: the stamp is immutable provenance, not a mutable destination.

The stale-publication proof is schedule independent

Consider any finite interleaving of input, start, partial, complete, cancel, and publication events.

Base case: before any event, no obsolete generation has published.

Inductive step: assume the property holds through a prefix. For the next event:

• if it does not publish, the property is unchanged;
• if its generation equals $g_{current}$, it is not obsolete at admission; or
• if its generation differs, the guard rejects it.

Advancing $g_{current}$ never decreases it, so an older generation cannot become current again. By induction, no obsolete query alters visible state in any finite completion order.

The proof does not depend on which worker ran first, how long a network request took, or whether cancellation succeeded. That is its value: adversarial scheduling becomes another test input rather than an unmodeled hazard.

Wraparound would violate monotonicity. A fixed-width counter therefore needs a proved lifetime bound, a wider epoch, or an equality token whose identity is never reused while an old task can survive. “The counter probably will not wrap” is not part of the proof.

Publication safety and resource safety are different laws

The generation gate makes obsolete work visibly inert. It does not stop that work from consuming CPU, memory, battery, worker slots, or network capacity.

Model one query as a finite root that owns a bounded set of child tasks. Each child begins pending and reaches exactly one terminal settlement:

$$\{complete, partial, refused, unavailable, canceled\}.$$

Terminal means terminal: a child cannot settle twice or return to pending. The root settles only when every admitted child is terminal and no detached work retains a capability to commit.

The word canceled is earned only when the child has lost every commit route. At least one of these must be true:

• scheduled work was withdrawn before execution;
• the capability needed to publish or consume a resource was revoked; or
• the child reached a terminal event that the owner joined and rejected.

Sending a cancellation request proves only cancel-requested. Conflating that with canceled hides both resource leaks and second publication channels.

A query is a finite task DAG

Several sources may contribute to one answer: lexical documents, commands, preferences, recent items, or a semantic index. Their dependencies form a directed acyclic graph. An edge $u\rightarrow v$ means $v$ cannot begin until $u$'s required output is available.

This graph describes semantic concurrency: nodes without a path between them may overlap without changing the meaning. It says nothing about how many threads exist. One event loop can execute independent nodes serially; a bounded pool can overlap them; a remote service can implement one node internally with many machines.

One worker per index is therefore a policy, not a theorem. It may increase parallelism, but it also adds startup, queue, memory, serialization, and contention costs. A small finite pool can execute the same task DAG with the same generation and settlement laws.

Work and span bound the possible speedup

With $P$ identical workers, any schedule needs at least

$$T_P\geq \max(W/P,S).$$

The work bound holds because $P$ workers perform at most $P$ units per time unit. The span bound holds because tasks along one dependency path must occur in order.

For a greedy work-conserving schedule over unit tasks, divide time steps into two kinds. In a full step, all $P$ workers run, so there are at most $W/P$ such steps. In a nonfull step, every ready task runs; at least one task on a remaining critical path must therefore complete, so there are at most $S$ nonfull steps. Hence

$$T_P\leq W/P+S.$$

Brent's simulation lemma states a sharper form for a synchronous parallel computation with $q$ operations across $t$ steps:

$$T_P\leq t+(q-t)/P.$$

The symbols are not a latency promise. Real tasks have unequal costs, communication, queues, failures, memory limits, and effect boundaries. The bounds explain what a schedule can possibly gain before measurement decides which execution policy is worthwhile.

Fan-out consumes a query-wide admission budget. If thirty indexes each receive the entire time, memory, and result cap, “bounded child” still creates an unbounded product as indexes are added. Reserve child credits from one root budget, reject excess children explicitly, and return partial settlement rather than hiding omitted work.

Top-k of top-k needs a proof

Each child may return its local top $k_i$. A merger cannot assume the global top $k$ is present unless child bounds certify that no omitted candidate can beat the current threshold under the combined comparator.

This is the same lesson as bounded aggregation earlier in the book. Independent caps compose only through a conservation law or a score upper bound. Without one, the result is an intentionally partial candidate answer, not the global top $k$.

Incremental publication can still be useful. It carries:

• the generation;
• terminal status of every admitted child;
• which source universes were searched;
• whether each source was capped;
• the comparator and policy version; and
• a stable identity for every result.

Those fields let the interface say “local results complete; semantic source pending” without turning a provisional prefix into an unqualified total answer.

Stable identity survives interleaving

Suppose a lexical child publishes document $d$, then a command child inserts an item above it. The row number of $d$ changes; its semantic identity does not. Selection, expansion, focus projection, and announcements reconcile by identity.

If a selected identity disappears, the product applies the successor rule declared in Chapter 21. It does not transfer selection to whatever item happens to occupy the old row. A partial settlement from one child likewise cannot erase an identity retained by another without the merger's explicit identity and dominance rules.

This is an order-maintenance problem around ranking, not an invitation for each worker to mutate a shared result array. Children publish immutable evidence; one deterministic fold produces the answer for the current generation.

Test every interleaving you can name

A deterministic adversarial scheduler makes the proof executable. Generate small DAGs, bounded worker counts, two or more query generations, partial and terminal child events, cancellation races, and every legal next-event choice.

Assert after every event:

• visible state carries the current generation;
• an obsolete event never changes visible observations;
• every admitted child is owned by exactly one root;
• each child has at most one terminal settlement;
• a settled root has no pending or detached child;
• resource credits never exceed the root budget; and
• result selection either preserves semantic identity or follows the declared successor rule.

Keep the smallest counterexample. The stale-result bug needs only two generations and reversed completion. A cancellation leak needs one child, cancel-requested, and an unjoined commit route. A top-k failure needs two sources whose locally discarded candidate would win globally.

Negative results

Lessons

• Completion order does not define publication authority.
• Every query and descendant event carries an immutable monotone generation.
• Only the current generation may change visible state.
• The generation gate proves visible safety under every completion interleaving.
• Cancellation requests do not prove terminal settlement.
• A query owns a finite task DAG and joins every admitted child exactly once.
• Semantic concurrency describes permissible overlap; worker count describes a physical execution policy.
• Work and span bound possible parallel speedup before machine costs.
• Fan-out and child caps reserve credit from one query-wide budget.
• Partial publication preserves provenance, settlement, and stable identity.

Practice

1. Enumerate every completion order for two generations with two children each and show which events may publish.
2. Construct a system where generation safety holds but a canceled child leaks resources indefinitely.
3. Prove the $W/P+S$ greedy-schedule bound by charging full and nonfull steps.
4. Draw one task DAG whose semantics are unchanged on one, two, and four workers, then calculate its lower bounds.
5. Give a two-source counterexample where top 1 of top 1 omits the global top 1 under a combined score.
6. Specify the settlement record for a query with one complete, one partial, one refused, and one canceled child.

References

1. Leslie Lamport. “Time, Clocks, and the Ordering of Events in a Distributed System.” Communications of the ACM 21.7, 1978.
2. Richard P. Brent. “The Parallel Evaluation of General Arithmetic Expressions.” Journal of the ACM 21.2, 1974.
3. Ronald L. Graham. “Bounds for Certain Multiprocessing Anomalies.” Bell System Technical Journal 45.9, 1966.
4. C. A. R. Hoare. “Communicating Sequential Processes.” Prentice-Hall, 1985.