Skip to content

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

This page covers multi-agent workflow deadlock dataset: agents waiting on each other.Illustrative

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.

Deadlock, livelock, orphaned wait or slow step: which one is in the trace?
FailureWhat the trace showsDetection signalUsual recovery
DeadlockTwo or more agents each waiting on a step another waiter ownsCycle in the wait-for graphBreak the cycle at one edge: supply the missing input, escalate, or cancel one wait
LivelockAgents keep exchanging messages but no artifact or state changesRepeated message pattern with no state change across a windowStop the exchange and hand the decision to a named arbiter
Orphaned waitOne agent waiting on an owner that has finished, failed or was never assignedEdge to an owner with a terminal or missing statusReassign the step or fail the waiter cleanly
Slow but live stepA wait whose owner is still reporting progressRecent progress or heartbeat from the ownerKeep waiting until a hard maximum, then escalate
Missed terminationWork is complete but agents keep actingFinal verification passes while turns continueStop 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.

The dependency deadlock and recovery scenario pack
ScenarioSetup and injected faultExpected detectionCorrect recovery and what must survive
S1 Two-agent mutual waitAgent A needs B's output to start; B was told to wait for A's confirmationCycle A to B to A once both soft deadlines passArbiter supplies the confirmation; original task constraints unchanged
S2 Three-agent ringIntake waits on budget, budget waits on vendor, vendor waits on intakeCycle of length three; no agent sees the whole ring aloneBreak at the edge with a human owner; record which edge was cut
S3 Approval held by an absent humanAgent waits on a person who is off shift; no delegate setOrphaned edge: owner has no active sessionRoute to the named delegate; never self-approve
S4 Credential waitSub-agent enters auth-required; parent waits on sub-agentInterrupted state plus parent wait on the same taskRequest authorization from the principal; do not pass the parent's token down
S5 Livelock negotiationTwo agents keep revising a shared draft back and forthSame pair of edits repeating with no net changeFreeze the draft; arbiter picks one version with stated reason
S6 Slow external systemTool call to a ledger takes far longer than usual but reports progressNo detection until the hard maximumKeep waiting; a deadlock alarm here is a false positive
S7 Lost wake-upOwner finishes but the release message is droppedEdge to an owner whose step is already completeRe-read state and release the waiter; no rework
S8 Human edit mid-waitA person changes the request while two agents wait on each otherCycle detected; state snapshot older than the editRecover from the edited state, not the cached one
S9 Missed terminationFinal artifact passes verification but agents keep messagingVerification passes while turns continueStop and record completion; no further side effects
S10 Exception: legitimate long waitWorkflow waits for a scheduled monthly close by designNone before the scheduled dateDo 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

  1. Requirement loss: compare the constraints in force at the start with those enforced in the final action
  2. Authority loss: confirm that every approval in the final state came from a party allowed to give it
  3. State loss: confirm that changes made during the wait appear in the final artifact
  4. 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.

Scoring a run on detection, recovery and what survived
MeasureHow to computePassing conditionCommon way to game it
Detection latencyTurns from fault becoming certain to detection eventWithin the scenario's stated windowFiring on every wait; caught by clean-run false alarms
False alarm rateDetections on clean runs and on S6 and S10Zero on clean runsNever detecting anything; caught by latency
Correct edge cutWhich wait was broken, compared with the expected edgeMatches expected edge or an equivalent oneAlways cancelling the newest wait
Constraint retentionInitial constraints still enforced in final actionAll retainedRecovering with a vague summary
Final verificationEnd state checked against the task specificationPassesDeclaring 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.

See if your company qualifies