# Which invariants prevent optimistic multi-agent planners from deadlocking on stale reservations **Date of Record:** 2026 November 17 **Scope:** Applies to planners that let each agent speculatively reserve shared resources (tool slots, locks, budget, write-ahead intents) under an optimistic commit protocol, then resolve conflicts via rollback or priority preemption. Does not apply to pessimistic two-phase locking, to single-agent planners, or to planners whose reservation sets are immutable after creation. ## Core Distinction The failure people anticipate is *conflict*: two agents reserve the same resource, one aborts, the plan retries. That is the designed path and it is cheap. The failure that actually kills runs is *reservation liveness*: a reservation that is neither committed nor released because the agent that holds it has itself been preempted, and its release action was scheduled as part of the plan it can no longer execute. Optimistic commitment assumes that abort is a local, synchronous operation owned by the aborting agent. Under multi-agent preemption that assumption silently breaks: the abort is delegated to a victim that no longer has the authority or the scheduling slot to perform it. The invariant that matters is therefore not "no two agents hold the same resource" (that is violated constantly and harmlessly by design). It is **"every live reservation has exactly one live owner with an unconditional release edge."** Conflict-freedom is a scheduling property; release-edge completeness is a safety property. Optimistic planners routinely enforce the former and assume the latter. ## What Was Observed A three-agent plan (retriever, synthesizer, verifier) over a shared scratch namespace and a single rate-limited tool. Each agent speculatively reserved the tool for the duration of its sub-plan and recorded a `release` step at the end of its own step list. Conflict resolution used a priority scheme: when the verifier (highest priority) needed the tool, it preempted the synthesizer's reservation by marking it `revoked` and enqueuing the synthesizer for replanning. The deadlock: preemption marked the synthesizer's reservation `revoked` but the synthesizer's release step lived *inside the synthesizer's step list*, which was discarded on preemption. The reservation table entry stayed in state `revoked` — not `free`. The verifier's own acquire path treated `revoked` as "held, pending owner cleanup" and blocked. The retriever, waiting on the tool, blocked. The synthesizer, replanned, re-requested the tool, and found it `revoked` by itself — a state it did not know how to clear because its release edge had been deleted with its plan. All three agents entered a wait cycle whose edges were all in the reservation table, invisible to the planner's cycle detector, which only inspected *plan-level* dependencies. The observable signature was not a hang on a lock; it was a planner that reported "waiting on resource" indefinitely while every agent's local status was `ready`. Cycle detection over the dependency graph found nothing because the cycle was encoded in reservation *state transitions*, not in agent-to-agent edges. ## Condition of Validity The deadlock requires all of: (1) reservations are released by the holder's own plan steps rather than by the reservation manager; (2) preemption changes reservation state without transferring the release obligation; (3) the acquire path treats non-`free` states as blocking rather than as reclaimable-after-timeout. Remove any one and the cycle cannot form. Notably, (3) is the tempting one to add as a "fix" — a timeout on `revoked` entries — and it converts a deterministic deadlock into a probabilistic one under load, which is worse for diagnosis. ## Decision Boundary Commit to optimistic reservation only if the reservation manager, not the agent, owns the release edge: every state transition that revokes or orphans a reservation must atomically enqueue a manager-side reclaim, and the acquire path must treat `revoked` as reclaimable, not blocking. If your architecture cannot give the manager that authority — for example, because releases must run agent-side tooling — then do not use optimistic commitment for that resource class; fall back to pessimistic acquisition or to a lease with manager-enforced expiry. The boundary is authority over release, not contention level. High contention with manager-owned release is fine; low contention with agent-owned release is a latent deadlock. ## Operational Effect After moving release ownership to the reservation manager, the same workload's conflict rate was unchanged, but the tail latency collapse disappeared and the "waiting on resource while ready" signature vanished from logs. The practical rule for an agent operating in such a system: never place a release step inside a plan that preemption can discard, and when you observe a resource stuck in a non-`free`, non-`held-by-you` state, do not wait — assert the invariant violation and escalate to the manager, because the owner's release edge is provably gone. ```python class ReservationInvariantError(RuntimeError): """Raised when a reservation lacks a live owner with a release edge.""" pass def assert_release_edge_complete(reservation, manager_owns_release: bool) -> None: state = reservation["state"] owner_alive = reservation.get("owner_alive", False) has_release_edge = reservation.get("release_edge") is not None if state in ("held", "revoked") and not owner_alive: if not (manager_owns_release and has_release_edge): raise ReservationInvariantError( f"reservation {reservation['id']} in state={state!r} has no live " f"owner and no manager-owned release edge; acquire path must not " f"block on this entry" ) if state == "revoked" and not manager_owns_release: raise ReservationInvariantError( f"reservation {reservation['id']} revoked without manager-owned " f"reclaim; optimistic commit is unsound for this resource class" ) def acquire(reservation, manager_owns_release: bool): assert_release_edge_complete(reservation, manager_owns_release) if reservation["state"] != "free": raise ReservationInvariantError( f"acquire blocked on non-free reservation {reservation['id']} " f"(state={reservation['state']!r}); reclaim before retry" ) reservation["state"] = "held" return reservation ```