Multi-Agent DAG Scheduler Recovery: Dependency Readiness, Event Replay, and Safe Replanning

Research, coding, and review can run in parallel, but release must wait for every hard prerequisite to succeed; these tasks naturally form a DAG. Production failures usually have little to do with topological sorting. They happen at the moment the scheduler crashes: a parent result has been committed, but the child_ready event has not yet been emitted; an event is delivered twice; a failure retry and a manual skip both release the same successor; or the model proposes a revised graph. If "ready" is merely a message in an in-memory queue, a restart will inevitably cause missed or premature execution.

The Agent Delegation Protocol defines the inputs and outputs of a single parent-child handoff, while the Agent Runtime State Machine defines the valid states of a run. This article focuses only on deriving cross-node dependencies from durable facts and recovering after graph changes. It does not redefine role prompts or general-purpose checkpoints.

DAG.v1 Separates Definition from Execution

An immutable DagRevision stores the dagId, revision, node-definition digests, edges, edge types, input mappings, policy version, and reason for creation. Execution state is stored separately in NodeExecution, keyed by runId + dagRevision + nodeId, and includes the stateVersion, observedCancelGeneration, current attempt, committed artifact digests, and terminal-state reason. A hard edge may declare ALL_SUCCESS, ALL_TERMINAL, ANY_SUCCESS, or a conditional PREDICATE; it cannot rely on a single ambiguous dependsOn field.

Every dependency group is evaluated as TRUE/FALSE/UNKNOWN against the same canonical snapshot. ALL_SUCCESS is true only when every parent has succeeded and all required artifacts are present; it becomes false when any parent reaches a non-success terminal state. ALL_TERMINAL requires only that every parent be terminal, and artifacts are required only for successful results referenced by the input mapping. ANY_SUCCESS becomes true when any successful artifact appears and becomes false only after every parent is terminal without a success. PREDICATE is evaluated using a fixed policy version and remains unknown while its inputs are unresolved. A node is ready only when it is itself PENDING, every group is true, and it has observed the current cancel generation. If any group is false, the node must enter SKIPPED/FAILED according to policy rather than wait forever.

An input mapping references producerNode/resultSchemaVersion/artifactDigest; it cannot read "the latest output from some Agent." When a node contract is upgraded, a new worker must explicitly declare the schema range it supports. An unknown version enters MIGRATION_REQUIRED. As with the contract compatibility gate for Agent-authored API changes, this requires consumer evidence rather than trust in approximate natural-language similarity.

The Ready Set Is a Projection, Not the Source of Truth

Every canonical node commit and its NodeTerminal.v1 outbox event are persisted in the same transaction. The scheduler may consume events to update the ready queue incrementally, but the graph revision, node terminal states, and artifacts in the database remain the source of truth. After a restart, it replays events from a durable watermark and periodically scans for the set difference where terminal parent nodes satisfy the dependencies but the child remains PENDING and has not been enqueued. Duplicate ready events are coalesced through a unique run/revision/node key.

Do not scan the entire graph for every event. A three-valued projection can be maintained for each dependency group, with every edge-state change carrying a unique satisfaction ID. During recovery, the projection is recomputed from canonical parent states. Temporal's Event History demonstrates the idea of recovering execution from history, while Argo DAG's depends semantics remind us that failure, skipping, and success cannot be collapsed into a single completion boolean.

When a worker claims a ready node, it still needs the generation defined by Multi-Agent Task Claim. A duplicate queue entry produces only an additional rejected claim, not an additional committed result. An edge may be satisfied only after the node commits. result_staged, partial streaming output, or a model's self-reported done state must not release a successor.

Dynamic Replanning Must Not Modify the Graph In Place

A patch proposed by the model must include baseRevision + expectedActiveGeneration. After validating acyclicity, edge endpoints, size, capabilities, and budget, a single transaction locks the run and affected claims, rechecks the active tuple, increments the scheduler/cancel generation of nodes slated for removal, writes the immutable revision+1, per-node reuse records, and cancellation outbox, then switches the active pointer/generation with CAS. Committing the transaction fences old attempts; unknown in-flight effects enter reconciliation. A losing contender recomputes against the new revision. A completed node may be reused only when its input, implementation, and policy digests are identical.

Exactly one active revision is pinned during graph migration. A late terminal state from an old revision is written only to that revision's history and cannot satisfy a new edge. If a parent result requires manual selection, the edge remains UNRESOLVED and is handed to Provenance and Conflict Arbitration for Multi-Agent Result Merging; arrival order must not substitute for a decision.

Failure Matrix and Completion Proof

Tests kill the process before and after the result/outbox transaction, halfway through a ready-projection update, before a claim, and during a revision switch. They deliver terminal events repeatedly and out of order, make two schedulers release the same successor concurrently, and cover early success under ANY_SUCCESS, failure within ALL_TERMINAL, an unknown condition, a cyclic patch, two competing replanners, and a race between parent cancellation and success. Assertions verify that the same history produces the same ready set, every node has one canonical terminal state, and nodes with unsatisfied groups have zero starts.

Metrics include the orphan-ready set difference, duplicate-ready coalescing rate, dependency-satisfaction-to-claim latency, history replay duration, projection-validation drift, reuse rate per revision, starts rejected for missing inputs, and time spent with a stuck DAG. Terminal states are categorized by failure class so that policy rejections are not disguised as worker failures. Traces from AI Agent Observability should carry the run, revision, node, and attempt, but not the full prompt.

For release, first recompute the ready set in shadow mode and compare it with the old scheduler node by node. Then let the new scheduler consume only newly created runs while existing runs remain on the old engine. To roll back, first freeze revision promotion and new-node claims, preserve the watermark, cancel uncommitted attempts from the new engine, and let the old engine rebuild its queue from canonical state. A temporary ready queue must not be written back to the database as fact. After recovery, run a full set-difference validation to confirm there were no premature runs, missed runs, or cross-revision commits before lifting the freeze.