Deadlock, Livelock, and the Agent That Waits Forever

Multi-agent systems inherit every coordination failure from distributed systems, plus a few of their own. The difference is that a deadlocked thread pool announces itself with a stack trace, while deadlocked agents produce fluent, plausible activity that looks like work.

Four failures, each with a structural fix.

Deadlock: everyone is waiting

Agent A delegates to B and waits. B needs something only A can provide and asks. If A's implementation blocks on B's result, neither proceeds.

The agent version is subtler than the thread version because the "lock" is often implicit — a shared resource, a file, an approval, a queue item claimed and never released.

Fix: questions travel only up the hierarchy, never sideways or back down. An agent waiting on a subordinate must be able to receive a question from it as a result, not as a blocking call. Combined with a strict tree topology — no cycles in the delegation graph — deadlock becomes structurally impossible rather than merely unlikely.

Livelock: everyone is busy, nothing progresses

The more common and more expensive failure. Two agents pass a task back and forth, each concluding it belongs to the other. Or a reviewer and a writer cycle: revise, reject, revise, reject, with the objection restated in new words each round.

Nothing is stuck. Turns are consumed, tokens are spent, the transcript looks like diligent collaboration. Without a specific check, this runs until a budget stops it — and if there's no budget, it runs until someone notices the bill.

Fix: detect repetition explicitly. Hash each state — the task plus the current artifact plus the agent holding it. If a hash recurs, the system is cycling. That's a five-line check, and it catches what turn limits catch only much later and much more expensively.

Also: every handoff must record a reason that hasn't been used before. A rejection repeating a prior objection means no new information entered, and the cycle should be broken rather than continued.

The orphaned wait

A worker is dispatched and never returns — crashed, timed out, or waiting on something that will never arrive. The supervisor waits indefinitely, holding its context, its budget, and possibly a lock.

Fix: every delegation carries a deadline and a defined behavior on expiry. Proceed without that result, retry once, or escalate — but decided in advance, in code. ⚠️ The absence of a timeout on delegation is one of the most common structural defects in multi-agent systems, because it never shows up in testing where everything responds.

Convoy: everyone waiting on the same thing

Ten workers fan out, and all ten need the same rate-limited API. Nine wait while one proceeds. Throughput is one worker's worth, cost is ten workers' contexts held open.

Fix: a shared concurrency limit at the tool layer, sized to the actual constraint, plus — better — a cache. Ten workers requesting the same reference data should produce one call and nine cache hits. Convoys usually indicate that the fan-out dimension was chosen wrongly: work split by document but bottlenecked on one shared lookup should have fetched the lookup once, before fanning out.

🔍 Detecting all four

Three instruments, none expensive:

A run-level DAG. Record every delegation as an edge. Cycles are visible immediately, and so are the nodes with no returning edge — those are your orphans.

Progress, not activity. Track a definition of forward progress specific to the task: items completed, artifacts changed, findings added. An agent system consuming turns with flat progress is livelocked, and this is the single most useful alarm in a multi-agent deployment.

Wait-time attribution. For each agent, time spent computing versus waiting. High wait across many agents at once is a convoy; high wait for one is an orphan.

✅ The structural defaults

Most of this is avoidable by construction rather than detection:

• Strict tree topology; no cycles in delegation.
• Every delegation has a deadline and an expiry behavior.
• Questions go up only.
• Global budget covering the whole tree, not per-agent — otherwise a fleet of individually-well-behaved agents can still collectively burn everything.
• State-hash repetition detection on any loop involving more than one agent.
• Shared resources behind a cache and a concurrency cap.

The takeaway

Agent coordination failures look like productivity, which is what makes them expensive. Enforce a tree with deadlines on every delegation, let questions travel only upward, budget the whole tree rather than each participant, and measure progress rather than activity. Then a livelock shows up as a flat line within a minute or two, instead of as an invoice at the end of the month.