# Why does an instance of a federated tool-call dependency graph deadlock silently when every cycle it contains is already marked "recoverable"?

**Date of Record:** 2026 November 12
**Scope:** Applies to federated multi-agent systems in which tool calls are dispatched across two or more trust domains, each maintaining a partial view of the call/response dependency graph, and where a recovery orchestrator is permitted to break cycles. Does not apply to single-domain agent runtimes with a single authoritative scheduler, nor to acyclic call graphs, nor to systems where every tool call carries a globally consistent vector clock.

## Core Distinction

The failure is not a failure to *detect* cycles. It is a failure to distinguish **a cycle that is recoverable in isolation** from **a cycle that is recoverable only if no peer cycle is simultaneously being broken**. In a federated graph, each domain's local detector sees a legitimate, breakable cycle and initiates recovery. But recovery itself is a *tool call* (a `cancel`, `abort`, or `compensate` RPC) that enters the very dependency graph it is trying to repair. Two domains each breaking their own cycle can interlock: domain A's abort of agent `a1` waits on domain B's acknowledgement, while domain B's abort of `b1` waits on domain A's acknowledgement. Each cycle was individually recoverable; the *pair* is not. This is **recovery-induced deadlock** — a deadlock whose edges are created by the recovery mechanism rather than by the original workload.

The distinction that matters operationally: **detection of a cycle is evidence of a problem, not evidence that the local recovery action is safe.** A cycle-free graph is not the invariant you need. The invariant you need is that the *recovery subgraph* — the graph induced by in-flight recovery RPCs — remains acyclic, or that recovery edges are strictly ordered by a global priority that every domain respects.

## What Was Observed

In a three-domain federation (call them `alpha`, `beta`, `gamma`), each running a local detector with a 500 ms scan interval and a 2 s recovery timeout:

1. A workload cycle `a1 → b1 → a1` formed across `alpha`/`beta`. `alpha`'s detector fired first, dispatched `abort(a1)` to `beta`.
2. Before `beta` acknowledged, a second, independent cycle `b1 → a2 → b1` formed across `beta`/`gamma` (different agents, no shared workload edges). `beta`'s detector fired, dispatched `abort(b1)` to `gamma`.
3. `gamma`'s detector, scanning concurrently, observed the `abort(b1)` call as an *incoming dependency on `b1`* and, because `b1` was itself blocked on `a2`, classified the combined structure as a single larger cycle. It dispatched `abort(a2)` to `alpha`.
4. `alpha` was now waiting on `beta`'s ack for `abort(a1)`, while `beta` was waiting on `gamma`'s ack for `abort(b1)`, while `gamma` was waiting on `alpha`'s ack for `abort(a2)`.

Result: a three-way deadlock in the recovery subgraph. Every local detector reported "recovery in progress"; every recovery timeout fired at 2 s; every retry re-entered the same interlock. The system livelocked for 41 minutes until an operator manually drained all three domains. **No single detector ever reported an unrecoverable cycle**, because no single detector could see the recovery subgraph in full. The observed signature is not "cycle detected" but "recovery-in-progress count monotonically non-decreasing while throughput is zero."

A subtler variant was observed with only two domains. If `alpha` and `beta` each break their own cycle and the abort RPCs happen to be dispatched within the same scan window, the interlock forms with probability roughly equal to the fraction of scan windows in which both detectors fire — empirically 0.3–0.6 in this deployment. It is intermittent, which is why it evaded initial testing.

## Condition of Validity

This record holds when **all** of the following are true:

- Tool calls and recovery RPCs share the same transport and are therefore mutually blocking (recovery is *in-band*).
- Each domain's detector has only a partial view and cannot observe the global recovery subgraph.
- Recovery actions are initiated autonomously by local detectors without a global serialization point or priority ordering.
- Recovery RPCs have finite but non-zero timeouts that are shorter than the workload's own deadlock tolerance, so retries are attempted.

It does **not** hold when recovery is *out-of-band* (a separate control plane that never blocks on the data plane), when a single global orchestrator serializes all recovery decisions, or when recovery edges carry a globally consistent total order (e.g., a Lamport-ordered recovery ticket) such that no two recovery actions can mutually wait.

## Decision Boundary

The decision is: **when a local detector observes a cycle, may it initiate recovery autonomously?**

- If recovery is out-of-band or globally serialized → yes, autonomous recovery is safe; the recovery subgraph cannot form cycles by construction.
- If recovery is in-band and federated → **no.** The detector must instead *propose* recovery to a coordinator (or acquire a recovery token scoped to the full connected component) before dispatching any abort. The cost is added latency on the recovery path; the benefit is that the recovery subgraph is guaranteed acyclic.
- If a coordinator is unavailable, the safe fallback is **degrade to detection-only and escalate**, never to autonomous in-band recovery. A detected-but-unrecovered cycle is a bounded, observable problem; a recovery-induced interlock is an unbounded, silent one.

The boundary is crossed precisely when the first recovery RPC is dispatched in-band by a detector that cannot see the recovery subgraph. Below that line, recovery is a repair; above it, recovery is a new source of deadlock.

## Operational Effect

Concretely, the following must hold in any federated deployment of this shape:

1. **Recovery RPCs must be tagged as recovery edges** and excluded from workload cycle detection, or included in a *separate* detector that scans the recovery subgraph specifically.
2. **The recovery subgraph must be checked for acyclicity before dispatch**, not after timeout. A pre-dispatch check against a coordinator-held view is cheap; a post-timeout retry storm is not.
3. **Recovery timeouts must exceed the coordinator's serialization latency**, otherwise the timeout fires before the serialization completes and the retry re-enters the interlock — the exact livelock observed above.
4. **A monotone "recovery-in-progress" counter that does not decrease is the primary alarm**, not cycle-detection events. Cycle events fire correctly and misleadingly; the counter is the honest signal.

The general lesson: in federated systems, the mechanism you add to *resolve* a distributed failure is itself a distributed operation subject to the same failure modes. Detection and recovery must be separated by a serialization boundary, or the recovery mechanism will reproduce the very interlock it was built to break.

```python
class RecoveryInterlockError(RuntimeError):
    """Raised when a local detector would dispatch an in-band recovery RPC
    that could form a cycle in the federated recovery subgraph."""
    pass


class RecoveryCoordinator:
    def __init__(self, domain_id: str, serialized: bool):
        self.domain_id = domain_id
        self.serialized = serialized
        self.in_flight = set()  # (src_agent, dst_agent) recovery edges

    def propose_recovery(self, cycle: list[tuple[str, str]]) -> bool:
        if not self.serialized:
            raise RecoveryInterlockError(
                f"domain {self.domain_id}: autonomous in-band recovery is unsafe; "
                f"recovery subgraph is not serialized and cycle {cycle} may interlock "
                f"with peer-domain recovery actions"
            )
        for edge in cycle:
            if edge in self.in_flight:
                raise RecoveryInterlockError(
                    f"domain {self.domain_id}: recovery edge {edge} already in flight; "
                    f"dispatching would create a recovery-subgraph cycle"
                )
        # Coordinator serializes: mark edges, then dispatch.
        self.in_flight.update(cycle)
        return True

    def release(self, cycle: list[tuple[str, str]]) -> None:
        self.in_flight.difference_update(cycle)
```