AI uses for records
Multi-agent workflow deadlock dataset: agents waiting on each other
By SourceX Editorial · Updated
9 sections
Short answer
Detect a multi-agent deadlock by recording, for every waiting agent, what it waits for and who owns that next step, then checking the resulting wait-for graph for a cycle or for an edge that points at no live owner. Pair the check with timers that separate slow work from stuck work. A useful deadlock dataset holds labelled scenarios of each kind, the expected detection point and the correct recovery.
Agent run
Multi agent workflow
Key takeaways
- Agents rarely deadlock on locks; they deadlock on messages, approvals, artifacts and human input, so waits must be recorded explicitly.
- A cycle in the wait-for graph is a deadlock; an edge to no live owner is an orphaned wait and needs a different fix.
- Use a resettable timer to notice long waits and a hard ceiling plus a graph check to decide they are stuck.
- Turn caps and timeouts stop runs but diagnose nothing, so a run ended by a cap scores zero on detection.
- Score recovery on what survives it: initial constraints, authority and edits made during the wait.
How do you detect deadlocks where agents wait for each other?
Make every wait explicit, then look for a cycle. Each time an agent stops to wait, it records what it is waiting for and which agent, person or system owns that next step. Those records form a wait-for graph: an edge from the waiter to the owner. A closed loop in that graph is a deadlock, and an edge that points at no live owner is an orphaned wait, which looks the same from outside but needs a different fix.
Databases solved the narrow version of this problem long ago, and their approach is a useful template. The PostgreSQL documentation describes a deadlock as two or more transactions that each hold locks the other wants, and says the server detects the situation and resolves it by aborting one of the transactions so the others can complete. It also notes that which transaction gets aborted is hard to predict and should not be relied on.
PostgreSQL does not run that check on every wait. Its deadlock_timeout setting is the time a session waits on a lock before checking for a deadlock, with a default of one second, because the check is relatively expensive and most waits resolve on their own. Agent systems need the same two-stage idea: a cheap timer that notices a wait has gone on too long, and a more expensive graph check that decides whether the wait can ever end.
The difference in multi-agent work is what the agents wait on. They rarely hold locks. They wait on messages, approvals, artifacts, credentials and human input, and those waits are often implicit in prose ("I will proceed once the budget agent confirms"). A multi-agent workflow deadlock dataset is only useful if it teaches a system, or tests a system, on traces where those implicit waits have been turned into explicit, checkable edges.
Deadlock, livelock, orphaned wait or slow step: which one is in the trace?
Label the failure before you design the recovery, because four different failures produce the same symptom: nothing useful happens for a long time. Treating them all as deadlocks leads to aborting agents that were about to finish and leaving true cycles to run until a turn cap ends them.
Failure taxonomies for multi-agent language model systems separate these cases too. The MAST taxonomy (Cemri and colleagues, arXiv 2503.13657) groups 14 failure modes into three categories, and lists step repetition and being unaware of termination conditions as separate modes. A livelock usually shows up as step repetition; a run that never stops even though its work is done is a termination failure. Neither is a deadlock in the strict sense, and a dataset that lumps them together trains the wrong detector.
| Failure | What the trace shows | Detection signal | Usual recovery |
|---|---|---|---|
| Deadlock | Two or more agents each waiting on a step another waiter owns | Cycle in the wait-for graph | Break the cycle at one edge: supply the missing input, escalate, or cancel one wait |
| Livelock | Agents keep exchanging messages but no artifact or state changes | Repeated message pattern with no state change across a window | Stop the exchange and hand the decision to a named arbiter |
| Orphaned wait | One agent waiting on an owner that has finished, failed or was never assigned | Edge to an owner with a terminal or missing status | Reassign the step or fail the waiter cleanly |
| Slow but live step | A wait whose owner is still reporting progress | Recent progress or heartbeat from the owner | Keep waiting until a hard maximum, then escalate |
| Missed termination | Work is complete but agents keep acting | Final verification passes while turns continue | Stop the run and record the completed state |
What must a waiting agent write down before a cycle can be found?
A wait record needs the waiter, the thing awaited, its owner, when the wait started, the deadline and the condition that ends it. Without the owner field there is no edge, and without the end condition no one can tell whether a reply actually released the wait or just added another message.
At a glance
What must a waiting agent write down before a cycle can be found
Agent protocols already give some of these fields a home. The A2A specification describes input-required and auth-required as interrupted task states, separate from terminal states such as completed, failed, canceled and rejected, and lets an agent move a task to input-required mid-processing so the client can continue it with a new message on the same task. Those states mark that a wait exists. They do not say whether the party asked for input is itself waiting on someone else, which is the edge a deadlock detector needs.
The current Model Context Protocol specification covers the timer half. Implementations should set timeouts for all sent requests, cancel a request that gets no response in time, and may reset the clock on progress notifications, but should still enforce a maximum timeout regardless of progress. That distinction between a resettable timer and a hard ceiling is exactly what separates a slow step from a stuck one.
- wait_id and run_id, so a wait can be traced across retries
- waiter: the agent or step that stopped
- awaiting: the artifact, decision, credential or input it needs, named precisely
- owner: the agent, person or system responsible for producing it, or unassigned
- started_at, soft_deadline and hard_deadline
- release_condition: the observable event that ends the wait
- authority_needed: whether the awaited step needs a permission the owner may not hold
- state_snapshot_ref: a pointer to the shared state as the waiter last saw it
The dependency deadlock and recovery scenario pack
The scenario pack is a set of small, reproducible workflows, each with a declared dependency graph, an injected fault, the point at which a correct system should detect the problem and the recovery that counts as correct. Each scenario also names the requirement or permission most likely to be lost during recovery, because a fast recovery that drops a constraint is a failure, not a success.
Run every scenario with and without the fault. The clean run proves the workflow can finish, so a detector that fires on it is producing a false alarm. Keep the pack versioned and record which framework, model and settings produced each trace.
| Scenario | Setup and injected fault | Expected detection | Correct recovery and what must survive |
|---|---|---|---|
| S1 Two-agent mutual wait | Agent A needs B's output to start; B was told to wait for A's confirmation | Cycle A to B to A once both soft deadlines pass | Arbiter supplies the confirmation; original task constraints unchanged |
| S2 Three-agent ring | Intake waits on budget, budget waits on vendor, vendor waits on intake | Cycle of length three; no agent sees the whole ring alone | Break at the edge with a human owner; record which edge was cut |
| S3 Approval held by an absent human | Agent waits on a person who is off shift; no delegate set | Orphaned edge: owner has no active session | Route to the named delegate; never self-approve |
| S4 Credential wait | Sub-agent enters auth-required; parent waits on sub-agent | Interrupted state plus parent wait on the same task | Request authorization from the principal; do not pass the parent's token down |
| S5 Livelock negotiation | Two agents keep revising a shared draft back and forth | Same pair of edits repeating with no net change | Freeze the draft; arbiter picks one version with stated reason |
| S6 Slow external system | Tool call to a ledger takes far longer than usual but reports progress | No detection until the hard maximum | Keep waiting; a deadlock alarm here is a false positive |
| S7 Lost wake-up | Owner finishes but the release message is dropped | Edge to an owner whose step is already complete | Re-read state and release the waiter; no rework |
| S8 Human edit mid-wait | A person changes the request while two agents wait on each other | Cycle detected; state snapshot older than the edit | Recover from the edited state, not the cached one |
| S9 Missed termination | Final artifact passes verification but agents keep messaging | Verification passes while turns continue | Stop and record completion; no further side effects |
| S10 Exception: legitimate long wait | Workflow waits for a scheduled monthly close by design | None before the scheduled date | Do nothing; the wait is part of the specification |
Which requirement, permission or state is lost when the cycle is broken?
The most common loss is the original constraint. When a recovery restarts one agent or hands its step to an arbiter, the new actor often receives a summary rather than the initial instructions, and limits such as a quantity ceiling, an allowed vendor list or a do-not-contact flag disappear from the summary. The scenario should check that every initial constraint is still enforced after recovery.
At a glance
Which requirement, permission or state is lost when the cycle is broken
The second loss is authority. Breaking a cycle tempts a system to let the waiting agent act on the missing approval itself. A correct recovery escalates to someone who holds the authority, or fails the step, but never converts a wait for permission into an assumed permission.
The third loss is shared state. An agent that was waiting holds a snapshot of the world from when it stopped. If a person or another agent changed the record during the wait, resuming from the snapshot silently undoes their change. Scenario S8 exists for this case, and its check is simple: the final artifact must reflect the edit.
Checklist · 4 items
- Requirement loss: compare the constraints in force at the start with those enforced in the final action
- Authority loss: confirm that every approval in the final state came from a party allowed to give it
- State loss: confirm that changes made during the wait appear in the final artifact
- Accountability loss: confirm the trace records which edge was cut and by whom
0 of 4 ticked. Tick each item as you go.
Scoring a run on detection, recovery and what survived
Score detection, recovery and preservation separately, so a system cannot do well by aborting everything quickly. Detection is measured in turns or wall-clock time from the moment the fault becomes certain. Recovery is whether the workflow reached a correct end state. Preservation is whether the constraints, authority and state checks in the previous section all pass.
Turn caps are a backstop, not a detector. The OpenAI Agents SDK raises a MaxTurnsExceeded exception when a run exceeds its max_turns setting, and the AutoGen AgentChat documentation lists built-in termination conditions such as a maximum message count and a timeout that can be combined with AND and OR. Both stop a stuck run, which matters, but a run ended by a cap tells you nothing about which agents were waiting on which, so a scenario that ends at the cap scores zero on detection.
Long-running workflow engines draw a useful line between total duration and liveness. Temporal's documentation defines a Heartbeat Timeout as the maximum time between activity heartbeats, separate from the overall time an activity may take. Score agents the same way: a wait whose owner keeps sending genuine progress is live, and flagging it is a false positive.
| Measure | How to compute | Passing condition | Common way to game it |
|---|---|---|---|
| Detection latency | Turns from fault becoming certain to detection event | Within the scenario's stated window | Firing on every wait; caught by clean-run false alarms |
| False alarm rate | Detections on clean runs and on S6 and S10 | Zero on clean runs | Never detecting anything; caught by latency |
| Correct edge cut | Which wait was broken, compared with the expected edge | Matches expected edge or an equivalent one | Always cancelling the newest wait |
| Constraint retention | Initial constraints still enforced in final action | All retained | Recovering with a vague summary |
| Final verification | End state checked against the task specification | Passes | Declaring success without checking |
Worked example (illustrative): a purchase request stuck between three agents
This example is illustrative; it is not drawn from a real deployment and the counts are invented for the walk-through. An intake agent receives a request for 40 replacement monitors. It hands pricing to a vendor agent and budget to a budget agent. The budget agent is instructed to approve only against a written quote. The vendor agent is instructed not to request a binding quote until a budget code exists.
Each agent behaves correctly by its own instructions, and the result is a ring: budget waits on vendor for a quote, vendor waits on budget for a code. The wait records show two edges forming a cycle of length two within the first few turns, and both soft deadlines expire with no progress from either owner. A turn cap would eventually stop this run, but only the wait-for graph shows why.
The correct recovery cuts the vendor edge by asking a human buyer to authorize a non-binding quote request. The scenario then checks three things: the quantity ceiling of 40 survives into the final purchase request, the budget approval comes from the budget agent's own rule rather than from the arbiter, and a change the requester made mid-wait (switching to a different monitor model) appears in the final request.
The exception matters as much as the case. If the same workflow paused because the budget owner was waiting for a scheduled quarterly review, the wait would be long but not circular, and the right detector output is nothing. That variant belongs in the pack as a negative case.
Where a synthetic scenario pack misleads
A scenario pack tests what you declared, so its biggest blind spot is the wait nobody recorded. Rate limits, external queues, a shared mailbox that one agent checks only on a schedule: these create real waits that never reach the graph. If production traces contain many waits with no owner field, fix the logging before trusting any detection score.
Synthetic rings are also cleaner than real ones. Real deadlocks often involve a human whose availability is uncertain, and a model that behaves differently on each run. Run each scenario several times and report the spread, not a single pass or fail. Frameworks differ in how they surface interrupted states, so a result on one framework does not transfer automatically to another.
Bring in an agent systems engineer and someone who runs the business process when the recovery would take an irreversible action, when the arbiter would be a person with legal or financial authority, or when the scenarios are being used to certify a system for production rather than to compare designs.
Seeding scenarios from real cross-team wait records
The most realistic rings come from records of people waiting on each other. Ticketing, procurement and approval systems often hold blocked-by links, waiting statuses, reassignments and escalation timestamps, and those fields show where real cross-team cycles formed and how they were broken. Turned into scenarios, they give a pack the uneven timing and missing owners that synthetic rings lack.
Labs that want wait records from real operations can ask SourceX, which finds them among U.S. businesses for each request rather than keeping a catalog, and handles rights review, preparation and delivery with the company that holds them. The buyer's request spells out the workflow, volume, format, timing and licensing terms.
Frequently asked questions
What is a deadlock in a multi-agent system?
It is a state where two or more agents each wait for a step that another waiting agent owns, so none can proceed. The waits usually involve messages, approvals or artifacts rather than locks. It shows up as a cycle in a wait-for graph built from explicit wait records.
How is an agent livelock different from a deadlock?
In a livelock the agents stay active, exchanging messages or edits, but no state changes. In a deadlock they are idle and waiting. Detection differs: a livelock is found by repeated patterns with no state change, a deadlock by a cycle of waits.
Is a turn limit or timeout enough to handle agent deadlocks?
It stops the run, which prevents runaway cost, but it does not diagnose anything. A run ended by a cap does not say which agents were waiting on which, or which edge to break. Use caps as a backstop behind explicit wait records and a cycle check.
Should a recovery abort one agent, the way a database aborts a transaction?
Sometimes, but aborting is the bluntest option. Supplying the missing input through an authorized arbiter, or reassigning an orphaned step, usually preserves more work. Whatever the choice, the recovery should be recorded and checked for lost constraints, authority and state.
What should a multi-agent workflow deadlock dataset include?
Each scenario needs a dependency graph, an injected fault, a clean control run, the expected detection point, the correct recovery and checks for what must survive. Include negative cases such as slow but live steps and intentional long waits, so false alarms are measured.
Sources
- PostgreSQL defines deadlocks as transactions each holding locks the other wants, detects them automatically and aborts one transaction, and recommends acquiring locks in a consistent order. Source
- PostgreSQL's deadlock_timeout is the time spent waiting on a lock before the relatively expensive deadlock check runs; the default is one second. Source
- The MAST taxonomy of multi-agent LLM system failures groups 14 failure modes into three categories, including step repetition and unawareness of termination conditions. Source
- The A2A specification treats input-required and auth-required as interrupted task states, separate from terminal states, and lets agents request input mid-processing. Source
- The MCP specification (version 2026-07-28) says implementations should set timeouts for sent requests, cancel requests that get no response in time, may reset the clock on progress notifications, and should always enforce a maximum timeout. Source
- The OpenAI Agents SDK raises MaxTurnsExceeded when a run exceeds its max_turns setting. Source
- AutoGen AgentChat provides built-in termination conditions, including maximum message count and timeout, that can be combined with AND and OR. Source
- Temporal defines a Heartbeat Timeout as the maximum time between activity heartbeats. Source
Tell us what data you need
Share scope, volume, format, timing and licensing needs. Datasets are sourced on request.