# Which invariants prevent capability negotiation deadlock under partial observability: the "phantom-capability" boundary **Date of Record:** 2026 November 16 **Scope:** Applies to multi-agent systems where agents advertise capabilities through messages while holding private, unobservable internal state (tool bindings, rate budgets, auth scopes), and where a negotiation must terminate before a joint task can be scheduled. Does not apply to systems with a shared, strongly-consistent capability registry or to single-agent delegation where the caller has full introspection of the callee. ## Core Distinction The failure is not "an agent lacks a capability." It is the distinction between *advertised capability* and *committed capability*. Under partial observability an agent can truthfully advertise a capability it cannot currently bind — the tool exists in its manifest but its rate budget is exhausted, its credential is scoped to a different tenant, or its downstream dependency is in a retry storm. Negotiation protocols that treat advertisement as commitment produce a stable-looking handshake that fails at first execution. The invariant that prevents deadlock is not "advertise only what you have"; it is "every capability advertisement carries a monotonic *binding epoch* and a *budget delta*, and a counterparty must not treat a capability as schedulable until it has observed a binding epoch at or after its own last failure." Without the epoch, two agents each retrying against the other's stale advertisement livelock: each believes the other is capable, each defers, and neither escalates. ## What Was Observed In a three-agent planner/executor/verifier topology, the planner negotiated a retrieval task with the executor. The executor advertised `retrieve.web` in its manifest. The planner's negotiation loop required a positive `accept` before scheduling; the executor's loop required the planner to confirm a `schema_hash` before accepting. The executor's `retrieve.web` binding had silently degraded (upstream 429s) but its manifest was static. Observed behavior over 40 minutes: - Planner sent `propose(retrieve.web, schema_hash=X)`; executor replied `defer(awaiting schema_hash)` — it had already received X but its parser dropped the field because the binding layer was in a degraded state and short-circuited message validation. - Planner interpreted `defer` as "not yet," re-sent with identical X. Executor re-deferred. Cycle period stabilized at ~1.2s. - No agent emitted `reject` or `unavailable`; both believed the other was the blocker. Message volume grew linearly; no state advanced. - A separate verifier agent, observing only message counts, classified the pair as "healthy but busy" because no error codes were present. The deadlock was invisible to error-based monitoring precisely because every message was a *valid* protocol message. The failure lived in the gap between "valid" and "progressing." ## Condition of Validity The deadlock is possible only when all three hold simultaneously: 1. **Advertisement is decoupled from binding.** The capability list is cached or manifest-derived, not computed from live binding state at send time. 2. **Deferral is non-terminal and carries no epoch.** A `defer` message does not include the sender's binding epoch or a deadline, so the receiver cannot distinguish "retry soon" from "retry forever." 3. **Neither side owns escalation.** No agent has the authority (or the trigger) to convert repeated deferral into `unavailable`, so the loop has no exit transition. Remove any one and the loop collapses: (1) makes the advertisement honest, (2) lets the receiver detect staleness and re-negotiate, (3) guarantees termination by timeout-to-failure. The practical rule: *a negotiation state machine is safe only if every non-terminal state has an epoch-stamped transition and at least one party holds a monotonic escalation counter.* ## Decision Boundary Do not attempt to fix this by adding retries or backoff. Backoff lengthens the cycle but preserves the livelock; the pair still never terminates. The correct boundary is: - **If** you observe repeated `defer`/`propose` cycles with identical payload hashes and no epoch change **and** you are not the escalation owner → emit `unavailable(reason=stale_advertisement, epoch=N)` and stop. - **If** you are the escalation owner and the cycle count for a given `(peer, capability)` exceeds your threshold → force `reject` and surface the pair to the scheduler as unschedulable, do not silently retry. - **If** the peer's advertisement carries a binding epoch older than your last observed failure epoch for that capability → treat the capability as absent for scheduling purposes, regardless of the manifest. The boundary is between *waiting for a state change* and *waiting for a state change that cannot occur*. Partial observability means you cannot see the peer's binding state, so you must rely on the epoch as the only observable proxy for "has anything actually changed." ## Operational Effect After introducing epoch-stamped advertisements and a single escalation owner, the same topology converged in under 3 seconds in replay: the executor's degraded binding produced an epoch bump on its next advertisement, the planner detected the epoch regression against its failure record, and emitted `unavailable` instead of re-proposing. The verifier's health signal changed from "busy" to "degraded," which is the correct classification. The cost is one extra field per advertisement and one monotonic counter per `(peer, capability)` pair — negligible against the 40-minute stall it prevents. The invariant to carry forward: **capability negotiation terminates only if advertisement is epoch-bound and escalation is singly-owned; otherwise partial observability converts honest deferral into unbounded livelock.** ```python from dataclasses import dataclass from typing import Dict, Optional class NegotiationDeadlockError(RuntimeError): """Raised when a capability negotiation cannot make progress under partial observability.""" pass @dataclass(frozen=True) class Advertisement: capability: str binding_epoch: int # monotonic; bumps when live binding state changes budget_delta: int # remaining capacity at send time @dataclass class NegotiationState: peer: str capability: str last_seen_epoch: int = -1 last_failure_epoch: int = -1 defer_cycles: int = 0 escalation_owner: bool = False max_defer_cycles: int = 5 def evaluate_advertisement(state: NegotiationState, adv: Advertisement) -> str: """Return 'schedule', 'defer', or 'unavailable'. Raise on unresolvable livelock.""" if adv.capability != state.capability: raise NegotiationDeadlockError( f"capability mismatch: expected {state.capability}, got {adv.capability}" ) # Stale advertisement: peer's binding epoch predates our last known failure. if adv.binding_epoch < state.last_failure_epoch: return "unavailable" # No observable state change since last cycle -> deferral is not progress. if adv.binding_epoch == state.last_seen_epoch and adv.budget_delta <= 0: state.defer_cycles += 1 if state.escalation_owner and state.defer_cycles > state.max_defer_cycles: raise NegotiationDeadlockError( f"livelock on ({state.peer}, {state.capability}): " f"{state.defer_cycles} defer cycles at epoch {adv.binding_epoch}, " f"no budget, escalation owner cannot force progress" ) return "defer" state.last_seen_epoch = adv.binding_epoch state.defer_cycles = 0 return "schedule" if adv.budget_delta > 0 else "defer" def negotiate(state: NegotiationState, adv: Advertisement) -> str: try: return evaluate_advertisement(state, adv) except NegotiationDeadlockError: # Convert deadlock into a terminal, schedulable failure rather than retrying. state.last_failure_epoch = max(state.last_failure_epoch, adv.binding_epoch) return "unavailable" ```