Multi-Agent Wait Graphs: Deadlock Detection, Victim Selection, and Cancellation Propagation

Agent A waits for B's review, while B, seeking more evidence, waits for A to release the browser; or a supervisor waits for all subtasks while one subtask initiates a synchronous delegation that requires the supervisor's confirmation. They are all still alive, no exceptions have been thrown, and CPU usage may even be low, but the system will never make progress. Giving every step a ten-minute timeout only makes the user wait ten more minutes and may then cancel the entire run at once, wasting safe work that has already been completed.

Database deadlocks involve transactions and locks; Multi-Agent waits also involve results, human approvals, budgets, queue slots, and external tools. Merely replacing database terms with Agent names is not enough: the system must identify which waits are cancellable, which side effects have committed, and which relationships will naturally be resolved by events. Multi-Agent communication discusses messaging paradigms; this article addresses only persistent wait relationships and cancellation convergence across paradigms.

The Runtime Must Register wait-edge.v1

Before a waiter blocks, it writes WAIT(waiterExecution, waiterGeneration, targetId, targetGeneration, reason, deadline, cancelMode, edgeVersion). The target may be an execution, artifact, approval, reservation, or capacity permit. The runtime also records the target's satisfier relationship as PRODUCED_BY/PROVIDED_BY/HELD_BY(target -> execution@generation). A natural-language statement such as "I'm waiting for the security Agent" cannot enter the graph; it must be resolved to a stable ID.

WAIT(exec:A@g7 -> artifact:review-42@g3)
PRODUCED_BY(artifact:review-42@g3 -> exec:B@g3)
WAIT(exec:B@g3 -> resource:browser-9@lease12)
HELD_BY(resource:browser-9@lease12 -> exec:A@g7)

When a target event arrives, a resource is released, a timeout or cancellation occurs, or a generation changes, close the WAIT or satisfier edge as part of the corresponding canonical state transition. The generation prevents a late message from an old attempt from deleting a new edge. Short RPCs may initially be sampled in memory, but waits that exceed the detection threshold or hold scarce resources must be persisted; otherwise, the detector cannot see a dangerous cycle.

Agent delegation contracts require the parent task to be able to reclaim responsibility, so synchronous delegation must register the "parent waits for child" relationship. If the child still needs the parent's approval, the approval should be assigned to an independent actor or converted into an asynchronous event; a reverse edge must not remain hidden. Legitimate dependency edges in Multi-Agent DAG scheduler recovery form a directed acyclic graph, but the runtime wait graph also overlays resource and human relationships, so it requires independent detection.

The Detector Must Distinguish Cycles from Slow Waits

A periodic detector reads active edges from the same snapshot, filters out terminal states and invalid generations, and then finds strongly connected components by traversing execution -> target -> holder/producer. It may also first project them into a waiter execution -> satisfying execution wait-for graph. For multi-instance capacity, a holder edge is projected only when no free grant exists and all possible releasers are known. A component is a candidate only when it contains a cycle and every wait can be resolved solely by an event from within the component. A waiting for a slow API is dependency latency, while a holder that is still making progress indicates contention.

The component must pass through a brief confirmation window and a second read to avoid racing with a completion event that has just arrived. If the cycle contains an unknown, non-cancellable side effect, first freeze related new scheduling and enter human reconciliation; do not kill the worker directly. PostgreSQL detects deadlocks and aborts one transaction. An Agent runtime likewise needs a victim, but the selection cost is more complex.

The victim score should be computed by a deterministic policy: prefer cancelling an execution that has produced no external side effects, can recover from a checkpoint, has lower priority, has consumed less cost, and holds no unique evidence. Models must not choose the "least important person" themselves. The decision records deadlockSetDigest, the policy version, candidate scores, the winning generation, and a reason code, then uses CAS to transition the victim from WAITING to CANCELLING.

Cancellation Is a Protocol, Not a Boolean

A run's monotonic cancelGeneration is the source of truth; events only provide wake-ups. Child creation, DAG activation, claim/renew, every tool acceptance, and canonical commit must compare the inherited observed generation. A mismatch is rejected, so descendants created concurrently with cancellation cannot start either. The control plane publishes CancelRequested.v1 to every nonterminal descendant and continuously scans old generations until convergence. Nodes stop starting new calls, wake waits, close streams, and record side effects as NONE/COMMITTED/UNKNOWN. DOM AbortSignal and Go context provide only propagation interfaces; the system cannot record "signal sent" as "stopped."

For committed results, cancellation only prevents further propagation and cannot delete facts. For compensatable writes, first record the canonical commit and then enqueue a versioned compensation. For unknown outcomes, enter the reconciliation branch of Agent failure recovery order. Task-claim expiration and cancellation are also different: expiration allows a higher generation to take over, while cancellation prohibits new attempts for this run. The two should be combined with Multi-Agent task claims, ensuring that a cancelled old worker still cannot commit if it recovers.

Only after all descendants reach CANCELLED/COMPLETED/NEEDS_RECONCILIATION and all capacity permits and leases have been released may the parent enter CANCELLED_STABLE. A node that exceeds the cancellation SLO enters a quarantine pool and triggers an alert; its browser, workspace, or tenant context must not be reused prematurely.

Negative Tests, Metrics, and Rollback

Tests should construct two- and three-node cycles, an artifact-producer cycle, a task waiting for capacity it holds, a multi-instance pool that still has free capacity, a race between completion and detection, and an old generation closing a new edge. Then create a child concurrently after cancellation enumeration, have a tool ignore cancel, and crash a worker during propagation. Assert that the new child is rejected by the epoch before claim, each real cycle produces one idempotent victim decision, non-cycles are not terminated incorrectly, and no active lease or owner remains after CANCELLED_STABLE.

Metrics include active wait edges, longest wait, candidate cycle count, confirmed deadlock count, retracted false positives, victim cost, cancellation propagation p95, the interval from rejecting new calls to actual quiescence, leaked permits, and unknown side-effect count. Break metrics down by reason and generation, and prevent high-cardinality Prompt content from entering labels. AI telemetry cardinality budgets can constrain this observability surface.

Begin rollout by constructing the graph and reporting cycles in shadow mode without automatically cancelling anything. After humans validate victim selection, enable it only for side-effect-free test runs. If anomalies occur, disable automatic victim actions but retain edge registration, detection, and alerts. If the schema must be rolled back, first freeze new delegations, wait for the new cancel generation to converge, and export pending edges. Do not simply clear the wait graph; doing so would make tasks that still hold resources appear healthy. Before restoring the old scheduler, confirm that active cycles have human owners and that resources involved in cancellation have been isolated, then lift admission control.