P1: #137 made dispatch order to a capacity-1 worker nondeterministic (60/60 → ~15% failure)

[kjgbot]

Found by the CI coverage change (#153/#154), which made the kernel suite run in CI for the first time. This test has never executed in CI before today.

The failure

worker_capacity::default_capacity_one_reopens_only_after_durable_completion_or_crash
kernel/relayflowd/tests/crash_resume/worker_capacity.rs:149
assertion `left == right` failed
  left: String("lane-a")
 right: "lane-b"

The spec declares two independent llm steps in the order [lane-b, lane-a], at default worker capacity 1. Line 149 asserts the first step.dispatch the worker sees is lane-b — the first-authored step.

Bisected to #137

Run in isolation, --exact --test-threads=1, same machine, same binary path:

commit	runs	failures
16860d2 (immediately before #137)	60	0
f16b133 (#137 itself)	15	1
current main	12	3

Combined at-or-after #137: 4 failures in 27 runs (~15%). Probability of observing 0 failures in 60 runs at that rate is ≈ 6e-5, so the clean "before" side is not luck.

It also fails on GitHub's runners — run 33816284259 — which is how it surfaced.

Mechanism

#137 replaced first-runnable-step selection:

-    for spec in &state.spec.steps {
-            StepState::Runnable => return start_actions(state, spec, runtime.attempts + 1, now_ms),

with a batch:

+    let starts = parallel::runnable_batch(state)
+        .into_iter()

runnable_batch returns every dependency-free step. Previously exactly one step was dispatched and it was the first in authored order; now both lanes are started, and a capacity-1 worker receives whichever reaches it first.

Note #137 added machine_starts_every_runnable_step_in_authored_order, which asserts authored order ["lane-b", "lane-a"] — but at the action level. The actions are ordered; what races is delivery to the worker. So the ordering contract this PR declared for itself is not the one observed at the socket.

Why this matters beyond a flaky test

RFC-0001's premise is a deterministic, replayable engine. If which step a capacity-bounded worker is offered first is nondeterministic, two replays of the same journal can dispatch in different orders. The exactly-once ledger keys on (step_id, idempotency_key, surface_path) and is not itself threatened, but dispatch order is an observable part of the contract, and a capacity bound that admits a race is the kind of thing that reads as "works" until it doesn't.

Whether the right repair is (a) restore authored-order selection under a capacity bound, or (b) decide ordering was never guaranteed and correct the test and the docs, is a design call — it should not be settled by whoever is closest to the red CI.

Not fixed here

Reported, not repaired, per the #153 work package: a newly-exposed failure is the deliverable, and the correct response is to name it rather than weaken the gate or quietly patch the test.

Reported by the v2 lead session; #137 was merged by me, so the repair wants a second pair of eyes.

🤖 Generated with Claude Code

https://claude.ai/code/session_01FtQSAcGDta5VH9xiZFT4sR

[kjgbot]

Narrowing: the kernel's ordering is fine, so this is in delivery

Tracing the path rules the scheduler out as the culprit:

machine/parallel.rs:72 — runnable_batch iterates state.spec.steps and pushes to selected in authored order:

for step in &state.spec.steps {
    ...
    selected.push((step, runtime));
}

For two llm steps surface_keys returns empty (machine/parallel.rs:91 — the let StepKind::Agent { .. } else { return Vec::new() } guard), so the conflict filter never removes anything. machine.rs:159 then flat_maps that batch into actions in the same order. So the kernel emits Dispatch(lane-b) then Dispatch(lane-a), ordered — which is exactly what #137's own machine_starts_every_runnable_step_in_authored_order asserts, and why that test passes while this one does not.

The capacity bound lives further down, in server/session/matching.rs:22:

(load < worker.capacity).then_some((worker, load))

If that predicate were evaluated between the two dispatches, the second would find load == 1, fail load < 1, and not be delivered at all — deterministically. The observed nondeterminism means the two dispatches are being matched against a stale load snapshot rather than sequentially, so a capacity-1 worker is offered both lanes and the winner is whichever send lands first.

That reframes the bug: it is not primarily an ordering wobble, it is a capacity bound that does not hold when a batch is dispatched from one state snapshot. runnable_batch returns every runnable step with no notion of how much worker capacity exists, which was safe when the caller dispatched exactly one and is not safe now.

Two candidate repairs, still a design call:

• bound the batch by available capacity at selection time, so the engine emits only as many starts as can be accepted; or
• make the match-and-reserve step atomic per dispatch, so the second match observes the first's reservation.

The second looks more correct — capacity is a property of the session layer, and teaching the pure state machine about live worker load would leak that concern into it — but it needs someone who owns the session code.

I have not attempted either. I merged #137, so the repair and its signoff should not both be mine.

[kjgbot]

What I ruled out, so the next person does not repeat it

Three layers are not the source of the reordering:

1. Batch construction — machine/parallel.rs:72 iterates state.spec.steps, a Vec in authored order, and pushes in that order. Deterministic.
2. Action emission — machine.rs:159 flat_maps that batch straight into actions. Deterministic, and asserted by kernel: dispatch runnable steps in parallel #137's own machine_starts_every_runnable_step_in_authored_order.
3. The drive loop — engine/drive.rs:140 consumes Action::Dispatch sequentially in a for loop, calling dispatcher.dispatch(...) one at a time. No concurrency, no reordering.

So by the time dispatch is attempted, the order is still lane-b then lane-a. The variance is introduced at or below dispatcher.dispatch, in the session layer.

That also weakens my earlier "stale load snapshot" hypothesis: if the loop is sequential, a reservation recorded by the first dispatch should be visible to the second, and matching.rs:15's doc comment claims exactly that ("capacity is counted across both journal-pending reservations and live assignments, so ... concurrent runs cannot overbook"). Either that invariant does not hold on this path, or the second dispatch is refused correctly and something else decides which of the two the worker observes first. I could not distinguish those two without instrumenting the session layer, and I stopped rather than guess further.

Worth checking first, for whoever picks this up: whether serve's background drive loop can also produce dispatches for the same run concurrently with the request-driven path — that is the one place a genuine race would fit the evidence.

The bisect and the ~15% reproduction rate in the issue body stand; only the proposed mechanism is narrowed.

[kjgbot]

Independent corroboration

A second agent hit this without being told to look for it. flows-pr139-rebase-codex-0904, working the #139 rebase against pinned main 27b7151, reported:

Disclosed inherited #137 timing test: capacity assertion failed intermittently on both pinned main (1/5) and rebased head, then final unchanged full gate passed.

1 failure in 5 on pinned main, from a different agent, a different worktree, and a different task — consistent with the ~15% rate measured here, and it independently attributes it to #137 rather than to the branch under test.

That is worth recording for two reasons. It rules out anything specific to my worktree or my rebase, and it shows the flake was already being absorbed as background noise by agents working other PRs — which is how a real regression stays alive. It only became a finding once CI started running the suite.

[kjgbot]

Second symptom: this also hits the SDK suite

The #139 signoff at 8b7148d found the same race manifesting through a different test in a different suite:

FAIL tests/live-kernel.test.ts > built flows CLI against live relayflowd
     > follows a live worker dispatch through flows run
FAILED [protocol_error] relayflowd could not complete the run request:
       relayflowd returned status parked without a classifiable completion

So #155 is not confined to crash_resume/worker_capacity.rs. It surfaces as a parked run with no classifiable completion when the SDK drives a live daemon — which means once CI runs both suites it can go red from two independent directions for one root cause. That raises the priority: an intermittent parked with no completionReason is much harder to recognise as this bug than a lane-a/lane-b assertion.

The reviewer ran a control at the main baseline 3725025 with the identical signature, so it is pre-existing rather than a #139 regression, and no #139 change touches the dispatch path — the only server.rs difference from main is internal_error → run_start_error on the engine.start mapper.

One caveat on the rates, stated because the report's numbers invite a wrong reading: 4/10 at #139's head versus 1/10 at the main baseline. Those are not distinguishable at n=10 (Fisher's exact p ≈ 0.15), so they are not evidence that #139 worsens the race, and nobody should treat them as such. They are consistent with the ~15% single-rate measured over 27 runs in the issue body.

Worth noting for whoever repairs this: parked without a classifiable completion is a plausible search term for anyone who has hit this in the last few weeks without diagnosing it.

[kjgbot]

Root cause found by instrumentation. Two of my earlier hypotheses were wrong.

I attempted a fix, measured it, and it did nothing (7/40 still failed). So I instrumented instead of guessing again. Recording both the dead ends and the actual mechanism, because the dead ends are individually plausible and someone will otherwise retry them.

Wrong hypothesis 1: stale load snapshot / capacity not enforced

Not the case. reserve_dispatch → select_worker_for_step enforces capacity correctly and sequentially:

PROBE reserve OK      step=lane-b attempt=1 workers=1
PROBE dispatch SEND   step=lane-b attempt=1
PROBE reserve REFUSED step=lane-a attempt=1 workers=1 reservations=0 assignments=1

lane-a is refused precisely because lane-b holds the single slot. Capacity works.

Wrong hypothesis 2: a later lane overtakes an earlier one refused in the same pass

Plausible — a pass now starts every runnable lane, so a worker registering between two reserve_dispatch calls could admit the second after the first was refused. I implemented order-preserving admission (refuse the rest of a worker class once one lane of that class is refused in a pass) and measured it: 7/40 still failed, versus ~15% before. No effect. Reverted; the tree is clean at ee28397.

The actual cause

The failing assertion is not the first dispatch of the run. It is worker_capacity.rs:149, retried = replacement.event("step.dispatch") — the first dispatch after run.resume, expected to be lane-b attempt 2, the retry of the lane whose worker was killed.

Probing the step states each time runnable_batch is computed, on a failing run:

PROBE batch states: [("lane-b", "Runnable"), ("lane-a", "Runnable")]
PROBE batch states: [("lane-b", "Done { Success }"), ("lane-a", "Runnable")]
PROBE batch states: [("lane-b", "Runnable"), ("lane-a", "Runnable")]
PROBE batch states: [("lane-b", "Backoff { attempt: 1, wake_at_ms: 1788502049984 }"),
                     ("lane-a", "Runnable")]
   → panicked at worker_capacity.rs:149

At the resume pass lane-b is in Backoff, not Runnable. So runnable_batch correctly returns only lane-a, lane-a is dispatched, and the test — which expects the crashed lane retried first — fails.

Whether lane-b or lane-a goes first is therefore a race between run.resume and lane-b's backoff wake_at_ms. Nothing about dispatch ordering is broken; a crashed step serves a retry delay, and a sibling can legitimately claim the free worker during that window.

The real question, which is a design call

run.resume is an explicit operator action meaning "recover this run now." Two defensible readings:

• Recovery preempts backoff. A crash-released lease is not a failed attempt that should be rate-limited; resume should fold it to Runnable before computing the batch. Then lane-b always retries first and the test is right as written.
• The test over-specifies. Backoff is backoff, siblings may proceed, and the assertion should not assume the crashed lane wins the worker.

I lean to the first — a delay meant to damp failing work should not apply to a worker that was killed — but this is exactly the kind of call that should not be made by whoever is closest to the red CI, and I merged #137.

Still unexplained

The bisect stands: 60/60 pass at 16860d2, ~15% fail at and after f16b133. But the mechanism above does not obviously depend on #137 — before it, the scheduler returned the first Runnable step, which with lane-b in Backoff would also have been lane-a. So why #137 changed the rate is not yet explained, and I would not treat the bisect as identifying the faulty line until that gap is closed. Possibly #137 shifted the timing enough to widen an already-present window rather than introducing the race.

No code change proposed. Tree clean at ee28397; all probes reverted.