Concurrency Bugs in Multi-Agent Systems: Races, Deadlocks, Idempotency

What you need to know

An agent that calls one tool, waits, and calls the next is a script with an expensive planner attached. Boring, and safe. The trouble starts the first time you let it call three tools in one turn to cut latency, hand three subtasks to three subagents, or retry a call that timed out. At that point you have built a distributed system, almost certainly without meaning to.

The failure modes are not new: lost updates, write skew, duplicate side effects, deadlock, retry storms. What is new is how hard they are to see. In a conventional service a race produces a stack trace or a corrupted row that somebody notices. In an agent system the planner is non-deterministic, so the same bug reproduces one run in twenty and never on the run you are watching — and the model narrates a plausible success over the wreckage.

This guide is deliberately unglamorous. It enumerates the six bug classes you will hit, gives the fix for each, goes deep on the intervention that pays for itself fastest — a properly derived idempotency key — and closes with a way to find these bugs on purpose.

Where concurrency enters an agent system

Most teams introduce concurrency six different ways within the first few months, and none of those decisions gets recorded as "we are now building a concurrent system". They get recorded as performance work, reliability work, or a product requirement.

Parallel tool calls in a single turn. Tool-calling APIs let a model emit several calls at once, and every serious runtime executes them concurrently for the latency saving. If two touch the same row, file or external record, you have a race inside what looks like one atomic step.

Fan-out to subagents. A supervisor splits work across workers. Each worker has its own context, its own tools, and — critically — its own view of shared state, captured at fan-out time and stale by the time the worker acts on it. See our guide to subagent orchestration in production.

Retries and timeouts. A timeout is a decision to stop waiting, not a guarantee that the operation stopped. When the client gives up at eight seconds and the tool completes at nine, the retry runs alongside an attempt that is still alive.

Background and durable jobs. Long-running work resumes from a checkpoint by design. If the checkpoint was written before the side effect but the side effect landed, the resume repeats it — the central hazard in durable execution for long-running agent jobs.

Human-in-the-loop approvals. An approval gate pauses one branch, sometimes for hours, and the world moves while it waits. When the approval lands, the agent acts on a plan formed against a world that no longer exists.

Multiple end users on one shared resource. The one everybody forgets. Two customer-service agents, driven by two humans, both working the same order. Nothing about your agent's design is concurrent; the deployment is.

The six entry points, and the first place each one bites.

Entry point	Introduced as	First failure you will see
Parallel tool calls in one turn	Latency optimisation	Lost update on a shared record
Fan-out to subagents	Throughput or specialisation	Write skew across stale snapshots
Retries after timeout	Reliability work	Duplicate side effect
Durable or background jobs	Long-horizon capability	Replayed side effect after resume
Human approval gates	Governance requirement	Action taken against a stale plan
Multiple users, one resource	Nothing — it is just traffic	Conflicting writes with no owner

The practical instruction is short. Before you optimise anything, write down which of these six your system already has. Most teams find four or five, and have reasoned about none of them.

Six bug classes, with the shape each one takes

Each of these has a textbook name, a symptom the user reports in entirely different words, and a reason it is unusually hard to spot when a language model sits in the middle of it.

Lost update: two agents read, both write, one write disappears

Two branches read the same record, each computes a new value from what it read, and each writes the whole record back. The second write overwrites the first. Nothing errors. The classic read-modify-write race, unchanged since multi-user databases first had to cope with it.

In an agent system it appears wherever a tool is shaped as "fetch the object, modify a field, save the object" — which is how most tools get written, because that is how most APIs read. Picture a Bengaluru lending platform running two parallel enrichment subagents against one application record: the credit-score field and the address-verification field are never both populated, and which one survives looks random.

It is hard to see because the losing write reports success: the subagent observed a 200 and told the supervisor the job was done. The only evidence is a field missing later, when the transcript is long gone.

The fix: stop writing whole objects. Narrow the write to the specific field, or use optimistic concurrency with a version column so the losing write fails loudly instead of quietly winning.

Duplicate side effects: the email sends twice

An operation completes, the acknowledgement is lost or arrives after the client has given up, the client retries, and the operation runs again. The customer receives two identical emails, the ledger carries two postings, the helpdesk shows two tickets for one complaint.

Agent systems make this worse three ways. Retries are configured generously because tool calls are flaky. Timeouts are set aggressively because interactive latency matters. And the agent may retry at the reasoning layer — it sees no confirmation in its context, decides the call failed, and calls the tool again. That bypasses every retry control in your HTTP client, because it is not an HTTP retry. It is a decision.

It is hard to see because duplicates are rarely reported as duplicates. They arrive as "your system double-charged me", weeks later, with no trace id.

The fix: idempotency keys, applied at the tool boundary and enforced server-side. This is important enough that it has its own section.

Stale reads and write skew across a fan-out

Write skew is the subtle one. Two subagents each read a snapshot, each check a constraint, and each find it satisfied. Both then write. Individually each write was legal; together they violate the invariant, because neither could see the other's pending change.

The canonical example is a rota: at least one engineer must remain on call, two people request leave, each check sees the other still rostered, both are approved, nobody is on call. Picture, equally, a Leeds logistics platform running two allocation subagents: it can commit the same pallet space twice, each branch having verified capacity against a snapshot where the other booking did not yet exist.

It is hard to see because there is no conflicting write to detect. The two writes touch different rows, so optimistic concurrency on either passes. The violated thing is a relationship between rows, and no per-row mechanism can see it.

The fix: materialise the constraint so the conflict becomes a write conflict. Introduce a row both branches must update — a capacity counter, a rota-coverage record — or enforce the check in a single transaction at an isolation level that detects it. Jepsen's consistency models reference maps what your database will and will not catch at each level.

Deadlock and lock convoy from inconsistent acquisition order

One branch takes lock A then wants lock B. Another takes B then wants A. Neither proceeds. Without timeouts the task hangs until someone kills it; with them you get a burst of failures that look like a slow dependency rather than a deadlock.

The agent-specific twist is that acquisition order is chosen by the planner, not by you. A hand-written service acquires locks in whatever order the code says, every time. An agent that updates the customer record before the order record on one run and the reverse on the next has produced two lock orderings from one prompt. You cannot enforce ordering in a prompt; enforce it in the tool layer.

The related pathology is the lock convoy: a coarse lock held across a long model call, with every other branch queued behind it. Throughput collapses to one branch at a time while your dashboards show healthy CPU and no errors.

The fix: a global lock-ordering rule applied inside the tool runtime — sort every lock set by a canonical resource identifier before acquiring — plus mandatory acquisition timeouts, plus a hard rule that no lock is ever held across a model call.

Cascading failure and retry storms

A dependency slows down. Every subagent hits its timeout at roughly the same moment because they all started together, and every subagent retries at the same moment because they share a backoff configuration with no jitter. The dependency, already struggling, receives a synchronised burst larger than the original load, with the retries of the retries behind it.

Fan-out is a load multiplier: eight subagents retrying three times each turn one user request into as many as thirty-two calls against a service sized for one. It is why an architecture that works beautifully in a one-user demo falls over at twenty.

It is hard to see because the first-order symptom sits on the dependency, not in your agent. Your traces show slow tool calls; the dependency's owner sees an unexplained traffic spike. The AWS Builders' Library article on timeouts, retries and backoff with jitter remains the clearest treatment of the mechanics.

The fix: jitter, retry budgets rather than per-call counts, and per-dependency circuit breakers. Details below.

Context and state divergence across branches

The one with no textbook name, because it is specific to systems where the state includes beliefs. Two branches of one task develop conflicting views — one subagent concluded the customer is in the UK, another India, because they read different fields — and the merge step, usually a supervisor prompt saying "combine these results", silently picks one. Frequently the longer one. Frequently not the correct one.

Picture a Mumbai payments team running parallel KYC and sanctions-screening subagents: it can end up with one branch operating on a verified identity and the other on an unverified one, and a supervisor summary that mentions neither the conflict nor which view it used.

It is hard to see because the merge produces fluent, plausible output. No exception, no conflicting write, no log line. The divergence is visible only if you compare the branches, which nothing does by default.

The fix: make the merge explicit and structured. Have each branch return typed facts with provenance rather than prose, reconcile in code rather than in a prompt, and raise a conflict when two branches assert different values for one field. Our guide to agent handoff contracts and state transfer covers the schema design.

The six bug classes at a glance.

Bug class	How the user describes it	Primary fix
Lost update	"The data I entered disappeared"	Field-level writes or optimistic concurrency
Duplicate side effect	"I was charged twice"	Idempotency keys enforced server-side
Write skew across fan-out	"Two people got the same slot"	Materialise the constraint into a contended row
Deadlock / lock convoy	"It just hangs" or "it got really slow"	Canonical lock ordering, timeouts, no locks across model calls
Retry storm	"Everything broke at once"	Jittered backoff, retry budgets, circuit breakers
Context divergence	"It contradicted itself"	Typed results with provenance, reconciliation in code

Idempotency keys are the single highest-leverage fix

If you do one thing from this guide, do this one. An idempotency key lets a caller retry safely by making a repeated request return the original outcome instead of performing the action again. It converts the hardest class of bug — silent duplicate side effects — into a non-event.

The key must be deterministic across attempts. That is the whole mechanism, and where most implementations go wrong. Derive it from the semantic identity of the intended action: task id, step id, tool name, canonicalised arguments. Exclude everything that varies between runs — the model's raw output text, a call-time timestamp, a fresh UUID, a retry counter. If any of those enter the key, every retry produces a new key and the mechanism does nothing while appearing to work.

Enforcement belongs on the server side of the boundary, in a store with a uniqueness constraint. A client-side cache is not enough, because the two attempts may not share a client — one of them is often a resumed job or a different process.

import functools
import hashlib
import json

DEDUP_WINDOW_SECONDS = 24 * 60 * 60


def idempotency_key(task_id: str, step_id: str, tool: str, args: dict) -> str:
    """Derive a stable key from the semantic identity of the action.

    Everything in here must be identical on a replay. Never include
    the model's raw output text, wall-clock time, a fresh UUID, or a
    retry counter -- those change every attempt and silently disable
    the whole mechanism.
    """
    canonical = json.dumps(args, sort_keys=True, separators=(",", ":"))
    material = "|".join([task_id, step_id, tool, canonical])
    return hashlib.sha256(material.encode("utf-8")).hexdigest()


class DuplicateInFlight(Exception):
    """A concurrent attempt holds the reservation for this key."""


def idempotent(tool_name, store):
    """Wrap a side-effecting tool so replays return the first result."""

    def decorator(fn):
        @functools.wraps(fn)
        def wrapper(*, task_id, step_id, **args):
            key = idempotency_key(task_id, step_id, tool_name, args)

            record = store.get(key)
            if record is not None:
                if record.state == "done":
                    # Replay: return the ORIGINAL result. Do not re-run.
                    return record.result
                raise DuplicateInFlight(key)

            # UNIQUE constraint on key makes this the arbitration point.
            if not store.reserve(key, ttl=DEDUP_WINDOW_SECONDS):
                raise DuplicateInFlight(key)

            try:
                result = fn(**args)
            except Exception:
                store.release(key)   # transient failure: allow a clean retry
                raise

            store.complete(key, result)
            return result

        return wrapper

    return decorator

Three details separate an implementation that works from one that looks like it works.

What you return on a replay. Return the stored result of the original execution, not a fresh one. A generic "already processed" marker is worse than useless: the caller gets a response shape it has never seen, treats it as a failure, and retries.

The dedup window. Twenty-four hours is a reasonable default. Choose it against how long a resumed job can legitimately lag. A durable job that can pause for three days needs a window longer than three days or its resume will double-execute.

Scope — the genuinely hard part. Too narrow and two distinct actions collide: if the key is only tool name plus arguments, a customer who orders the same item twice on purpose gets one order. Too broad and real duplicates slip through. Bind the key to the plan step that authorised the action: a second legitimate order is a new step id, a retry of the first carries the same one. Get step identity right and the key follows.

For reference implementations, read Stripe's documentation on idempotent requests and the AWS Builders' Library piece on making retries safe with idempotent APIs.

Guarding shared state

Idempotency stops you doing the same thing twice. It does not stop two different things trampling each other. For that, decide per resource how much concurrency you will tolerate. Work down this ladder and stop at the first rung strong enough, because every rung costs throughput.

Single writer by routing. The cheapest and most under-used option. Route every operation on a resource to one worker or queue partition, keyed by resource id. Concurrency across resources is untouched; on the same resource it is structurally impossible. The cost is that a hot resource becomes a bottleneck.

Optimistic concurrency control. Attach a version number or ETag to the resource, read it, and include it in the write. If the version has moved, the write fails and the caller re-reads and retries. Excellent when conflicts are rare, which in agent systems they usually are. The discipline is valuable in itself: you cannot write without saying what you believed.

-- The write is a no-op unless the row is still what we read.
UPDATE applications
   SET status  = :new_status,
       version = version + 1,
       updated_at = now()
 WHERE id      = :application_id
   AND version = :expected_version;

class ConflictError(Exception):
    """Contention outlasted the retry budget for this row."""


def update_with_cas(db, application_id, mutate, max_attempts=5):
    """Compare-and-swap with bounded retry. Raises on persistent conflict.

    sleep_with_jitter is defined in the retry section below.
    """
    for attempt in range(max_attempts):
        row = db.fetch_one(
            "SELECT id, status, version FROM applications WHERE id = %s",
            (application_id,),
        )
        if row is None:
            raise LookupError(f"application {application_id} not found")

        new_status = mutate(row)          # pure function of what we read

        changed = db.execute(
            "UPDATE applications SET status = %s, version = version + 1 "
            "WHERE id = %s AND version = %s",
            (new_status, application_id, row["version"]),
        )
        if changed == 1:
            return new_status

        # Someone else won. Re-read and recompute -- never blind-retry the
        # same write, because the value we computed is now based on a state
        # that no longer exists.
        sleep_with_jitter(base=0.05, attempt=attempt)

    raise ConflictError(f"application {application_id} contended out")

Advisory locks. When the work between read and write is too long to redo, take a real lock. Three rules make them survivable: every acquisition has a timeout, every lock set is acquired in canonical order by sorting resource identifiers, and no lock is held across a model call. Distributed locks carry real subtleties around expiry and fencing — Martin Kleppmann's analysis of distributed locking is required reading before you build one.

Serialise the step. When correctness beats throughput outright — anything moving money, anything with a regulatory record, anything irreversible — run the whole step in one serialisable transaction, or behind a single-threaded executor for that resource. Slow, boring, correct.

Guard options compared. Pick the cheapest rung that is strong enough.

Guard	Throughput	Complexity	Failure mode when it goes wrong
Single writer by routing	High across resources, capped per resource	Low	Hot partition; work queues behind one key
Optimistic concurrency (version / ETag)	High when conflicts are rare	Low to medium	Retry churn under contention; livelock without backoff
Advisory locks with timeout	Medium	Medium to high	Deadlock, lock convoy, orphaned lock on crash
Serialised step	Low	Low	Queue growth and latency; correctness preserved

Retries, timeouts and the storm you cause

Retries are the correct response to transient failure and the direct cause of the worst outages. Four rules keep them on the right side of that line.

Jitter is not optional. Exponential backoff without randomisation synchronises your callers into waves, which is exactly the traffic shape a struggling dependency cannot absorb. Full jitter — sleep a random duration between zero and the current backoff ceiling — spreads the load and is a two-line change.

Budgets, not counts. A per-call retry count of three sounds modest until eight subagents each apply it. Set a retry budget instead: a cap on retries as a proportion of total calls across the whole task, commonly around ten per cent. Google's SRE book makes the same case for a proportional client-side budget in its chapter on handling overload. When the budget is exhausted, calls fail fast rather than piling load onto a dependency that is already failing.

Circuit breakers per dependency. After a threshold of consecutive failures, open the circuit and fail fast for a cool-down period, then admit one trial call before closing. Martin Fowler's write-up of the circuit breaker pattern is the standard reference. The agent-specific requirement is that an open circuit reaches the planner as a structured, actionable error — "this tool is unavailable, do not retry" — not a generic failure the model reads as an invitation to try again.

A timeout must cancel the work. The rule that gets skipped. If your client stops waiting at eight seconds and the server keeps working, you have bounded nothing; you have created an invisible in-flight operation that completes after you have already retried. Propagate a deadline through to the tool, and make sure the tool honours it.

import random
import time


def sleep_with_jitter(base: float, attempt: int, cap: float = 20.0) -> None:
    """Full jitter: uniform(0, min(cap, base * 2**attempt))."""
    ceiling = min(cap, base * (2 ** attempt))
    time.sleep(random.uniform(0.0, ceiling))


class RetryBudget:
    """Task-wide cap on retries, expressed as a ratio of total calls.

    Per-call retry counts do not compose across a fan-out: eight
    subagents retrying three times each is up to thirty-two calls from
    one user request. A shared budget does compose.
    """

    def __init__(self, ratio: float = 0.1, minimum: int = 3):
        self.ratio = ratio
        self.minimum = minimum
        self.calls = 0
        self.retries = 0

    def record_call(self) -> None:
        self.calls += 1

    def try_consume(self) -> bool:
        allowance = max(self.minimum, int(self.calls * self.ratio))
        if self.retries >= allowance:
            return False          # fail fast; do not add load to a sick service
        self.retries += 1
        return True

If your traffic passes through a shared gateway, implement budgets and breakers there once rather than in every agent. Our guide to a resilient LLM gateway with failover, retries and rate limits covers the layout.

Testing for it: deterministic replay and fault injection

You will not find these bugs by running the happy path, and running it a thousand times will not help either. The interleaving that breaks you needs a specific tool response to be late, duplicated or lost — a combination that arrives roughly never in a test environment and roughly weekly in production. The method has three parts.

Record real traces. Capture complete traces from staging or production: every model response, every tool call, every tool result, with a task id and step id attached. This is the instrumentation you need for debugging anyway.

Replay with the plan pinned. Stub or replay the model responses so the plan is fixed. A non-deterministic planner renders a concurrency test meaningless, because any failure can be blamed on the model having done something different. Hold the plan constant and the remaining variance is yours.

Inject faults into the execution. With the plan fixed, vary the interleaving deliberately. Five fault types cover most real bugs: delay a response so another branch overtakes it; duplicate a call so the side effect happens twice; drop a response so the caller times out and retries; reorder two responses; and — the nastiest — succeed at the side effect but fail before the acknowledgement, the exact condition idempotency exists to survive.

import random
import time


class FaultInjectingTools:
    """Wraps a tool runtime and perturbs the execution, not the plan.

    Use with model responses replayed from a recorded trace so the
    plan is identical across runs and any divergence in outcome is
    attributable to the interleaving.
    """

    FAULTS = ("delay", "duplicate", "drop_response", "reorder", "ack_lost")

    def __init__(self, inner, seed: int, rate: float = 0.25):
        self.inner = inner
        self.rng = random.Random(seed)
        self.rate = rate
        self.deferred = []

    def call(self, name: str, **kwargs):
        fault = None
        if self.rng.random() < self.rate:
            fault = self.rng.choice(self.FAULTS)

        if fault == "delay":
            time.sleep(self.rng.uniform(0.5, 4.0))
            return self.inner.call(name, **kwargs)

        if fault == "duplicate":
            self.inner.call(name, **kwargs)      # side effect number one
            return self.inner.call(name, **kwargs)

        if fault == "drop_response":
            self.inner.call(name, **kwargs)      # it ran; caller never learns
            raise TimeoutError(name)

        if fault == "ack_lost":
            result = self.inner.call(name, **kwargs)
            self.deferred.append((name, result))  # delivered out of band later
            raise TimeoutError(name)

        if fault == "reorder" and self.deferred:
            i = self.rng.randrange(len(self.deferred))
            return self.deferred.pop(i)[1]

        return self.inner.call(name, **kwargs)

Run each scenario with many seeds — a few hundred usually surfaces the common classes — and assert an invariant rather than an output. This is the part people get wrong. The output was never what broke; it was fine, which is why nobody noticed. Assert that exactly one payment row exists for the task, that no lock is held after the run, that the status field only moved forward. Measuring reliability across repeated perturbed runs is covered in agent reliability with pass@k, perturbation and fault injection.

Invariants worth asserting

Write these as automated post-run checks in your replay harness and, where cheap enough, as continuous assertions in production. As of August 2026 this remains one of the few dependable ways to catch concurrency defects before a customer does, because it checks the world rather than the transcript.

Post-run invariants, what a breach means, and where to enforce it.

Invariant	What a breach indicates	Enforce at
No resource created more than once per step id	Missing or badly scoped idempotency key	Unique constraint in the store
State transitions are monotonic (no backward moves)	Lost update or a stale write winning	Version column plus a transition guard
No lock held after the task terminates	Orphaned lock from a crash or a missed release	Lock TTL plus a sweeper job
Total spend within the task budget	Retry storm or an unbounded planning loop	Task-scoped budget counter
Every side effect traces to exactly one step id	Untracked call path, or a reasoning-layer retry	Mandatory step id in the tool schema
No two branches assert conflicting values for one field	Context divergence and a silent merge	Typed reconciliation in code, not in a prompt

The last row deserves a note: it is the only invariant here with no equivalent in a conventional distributed system, and the one most likely to be violated in a system that passes every other check.

What to do next

Concurrency bugs in agent systems are not exotic. They are the oldest bugs in the industry, wearing a costume that makes them harder to recognise and a narrator that makes them harder to believe in. The remedies are correspondingly old and well documented, so you are not inventing anything.

A sensible order of work, whether you are in Chennai or Cardiff. Write down which of the six entry points your system already has. Put a mandatory idempotency key on every side-effecting tool and enforce it server-side; that one change removes the bug class causing the most customer harm. Choose a guard per shared resource, starting with single-writer routing. Replace per-call retry counts with a task-wide budget, add full jitter, and make every timeout genuinely cancel the work behind it. Build the replay harness, inject faults, and assert invariants rather than outputs. Finally, decide what happens when a guard trips — a blast-radius question, covered in our guide to agents that fail safe.

Agent reliability engineering is still a relatively scarce competence in both India and the UK as of August 2026, and unusually easy to evidence: a fault-injection harness with its list of invariants and the bugs it caught is a portfolio artefact no demo can imitate. If you have built one, put it on a Builder profile where the people hiring can find it.