Debugging multi-agent deadlocks with distributed tracing

Debugging multi-agent deadlocks is painful because the failure manifests as a silent hang rather than an exception. When autonomous agents call each other in cycles through LLM tool loops, you need distributed tracing to see where the wait graph closes. This guide walks through a concrete instrumentation and analysis workflow for debugging multi-agent deadlocks in production systems.

Step 1: Instrument each agent with trace context propagation

The first rule of debugging multi-agent deadlocks is to never trust agent logs alone. A deadlock is a distributed property: agent A waits on B, B waits on C, C waits on A. You need a single trace that crosses process boundaries.

Use OpenTelemetry and propagate the traceparent header on every inter-agent HTTP call and every LLM API request. Start by extracting context at your agent’s entry point:

from fastapi import FastAPI, Request
from opentelemetry import trace
from opentelemetry.propagate import extract

app = FastAPI()
tracer = trace.get_tracer("agent.service")

@app.post("/agent/run")
async def run_agent(request: Request):
    ctx = extract(request.headers)
    with tracer.start_as_current_span("agent.run", context=ctx) as span:
        span.set_attribute("agent.id", "planner")
        # dispatch to reasoning loop
        return {"status": "ok"}

If your agents call models through n4n.ai, its OpenAI-compatible endpoint spans 240+ models with automatic fallback when a provider is degraded. Propagate the traceparent header on each request so a fallback to a different provider doesn’t orphan the span.

Step 2: Emit spans for LLM calls and tool invocations

A deadlock often hides inside a tool-call loop: the LLM decides to call an agent-tool that calls another LLM, which calls back. Emit a client span for each LLM completion and each tool execution.

from opentelemetry.propagate import inject
import httpx
from opentelemetry.trace import SpanKind

def call_llm(messages, model="gpt-4o-mini"):
    with tracer.start_as_current_span("llm.generate", kind=SpanKind.CLIENT) as span:
        span.set_attribute("llm.model", model)
        headers = {}
        inject(headers)  # adds traceparent
        resp = httpx.post(
            "https://api.example.com/v1/chat/completions",
            json={"model": model, "messages": messages},
            headers=headers,
            timeout=30,
        )
        usage = resp.json().get("usage", {})
        span.set_attribute("llm.total_tokens", usage.get("total_tokens", 0))
        return resp.json()

Do the same for tool calls. Label the target agent explicitly so you can reconstruct the wait graph later:

def call_agent_tool(target_agent, payload):
    with tracer.start_as_current_span("agent.call") as span:
        span.set_attribute("target.agent", target_agent)
        span.set_attribute("payload.size", len(payload))
        # synchronous HTTP or async queue send

Step 3: Correlate spans across agents using a shared trace ID

After instrumentation, the next phase of debugging multi-agent deadlocks is correlating spans. All agents in one task must share the same root trace ID. In Jaeger or Tempo, query by the root service and operation:

curl "http://jaeger:16686/api/traces?service=agent.service&operation=agent.run&limit=20"

Each returned trace should contain agent.run (root), multiple llm.generate children, and agent.call spans that point to other services. If you see separate traces for what should be one task, your context propagation is broken—fix that before continuing.

A quick sanity check in Python:

def assert_single_trace(spans):
    trace_ids = {s["traceID"] for s in spans}
    assert len(trace_ids) == 1, f"found {len(trace_ids)} traces"

Step 4: Detect the deadlock cycle in the trace graph

A live deadlock shows up as open spans (no end time) that are children of an agent.call waiting on a downstream agent that is itself waiting. Pull the trace JSON and build a wait-for graph.

def build_wait_graph(spans):
    graph = {}
    for s in spans:
        if s.get("operationName") == "agent.call":
            caller = s["tags"]["agent.id"]
            callee = s["tags"]["target.agent"]
            graph.setdefault(caller, set()).add(callee)
    return graph

def has_cycle(graph):
    visited, stack = set(), set()
    def dfs(node):
        if node in stack: return True
        if node in visited: return False
        visited.add(node); stack.add(node)
        for nb in graph.get(node, ()):
            if dfs(nb): return True
        stack.discard(node)
        return False
    return any(dfs(n) for n in graph)

Run this on any trace where the root agent.run span has no end time after your expected timeout. If has_cycle returns True, you have confirmed a cyclic wait—the core of debugging multi-agent deadlocks.

Step 5: Break the deadlock with timeouts and explicit orchestration

Once you have the cycle, you break it by enforcing a maximum wait on every agent.call. Use asyncio.wait_for so a hung downstream agent raises instead of blocking forever.

import asyncio

async def call_agent_with_timeout(target, payload, timeout=15):
    try:
        return await asyncio.wait_for(
            send_agent_request(target, payload), timeout
        )
    except asyncio.TimeoutError:
        # break cycle: return sentinel, do not retry blindly
        return {"error": "deadlock_breaker", "agent": target}

For systems with many peer-to-peer agents, redesign the interaction to use a central orchestrator that owns the trace root and dispatches subtasks. The orchestrator can detect when a subtask has not reported a heartbeat span within N seconds and cancel the branch.

If you rely on LLM gateways, set a client routing directive that pins a cheap model for fallback paths so the timeout path is cheap. This keeps the system responsive when a provider is rate-limited.

Step 6: Verify the fix with synthetic load and trace assertions

Verification is not “it didn’t hang in my manual test.” You need automated proof that no trace contains an unclosed agent.run after a bounded period.

Write a load test that spins up concurrent multi-agent tasks:

import asyncio, random

async def simulate_task(i):
    # triggers planner -> researcher -> critic loop
    await call_agent_with_timeout("planner", {"task": i})

async def main():
    await asyncio.gather(*[simulate_task(i) for i in range(50)])

asyncio.run(main())

After the run, query your tracing backend for traces with agent.run duration > 60s and status not finished:

curl "http://jaeger:16686/api/traces?service=agent.service&operation=agent.run" \
  | python -c "import sys,json; d=json.load(sys.stdin); \
       open_spans=[s for t in d['data'] for s in t['spans'] \
       if s['operationName']=='agent.run' and 'endTime' not in s]; \
       print('OPEN SPANS:', len(open_spans))"

Success means OPEN SPANS: 0 and has_cycle is False on every sampled trace. If you still see cycles, revisit Step 2—some agent path is not emitting the target.agent tag, leaving the graph incomplete.

Step 7: Add a continuous deadlock guard

Debugging multi-agent deadlocks is a one-time investigation; preventing them is ongoing. Ship a background job that periodically fetches the last 100 traces, runs build_wait_graph + has_cycle, and alerts if a cycle appears. This turns a silent hang into a paging event.

Keep your span tags consistent: agent.id on every agent span, target.agent on every call. Without that discipline, the graph analysis in Step 4 becomes guesswork. Distributed tracing only helps if the metadata matches the actual control flow.