{
  "id": "oai:papers.qnfo.org:specification-induced-deadlock-in-zero-tolerance-agent-protocols-a-state-machine",
  "slug": "specification-induced-deadlock-in-zero-tolerance-agent-protocols-a-state-machine",
  "title": "Specification-Induced Deadlock in Zero-Tolerance Agent Protocols: A State-Machine Analysis of the Capability–Invocation Gap",
  "authors": [
    "Rowan Brad Quni-Gudzinas"
  ],
  "abstract": "Agent protocols written for large language model (LLM) agents increasingly mandate live tool execution and forbid simulated or placeholder actions outright. Such zero-tolerance semantics can create a specification-level deadlock: the agent recognizes that the required capability exists in its action space, but the protocol provides no representation for the case in which that capability is present yet its invocation is blocked in the current context, so the agent classifies every candidate action as a forbidden simulation and halts. This paper formalizes that failure mode. We model a protocol as a state machine over (requirement, capability, invocation) triples, define zero-tolerance compliance semantics over it, and prove that a halt state is reachable and absorbing whenever the protocol admits the configuration \"capability present, invocation blocked.\" We quantify the exposure: a binary-state protocol governing k permission-gated tools is specification-complete on only a (2/3)^k fraction of the true three-state space, giving 32/243 ≈ 0.132 at k=5 and a 57.7× state-space gap at k=10. We further show, by a reduction in the style of Rice's theorem, that deciding whether an arbitrary protocol halts compliantly is undecidable, so well-definedness must be built into the protocol's syntactic class. Under stated projection assumptions (a $0.1$ per-invocation probability that capability exists but invocation is blocked, and $5$ gated invocations per task), the per-task deadlock probability is $0.40951$. The result reframes a class of agent halts as specification defects repairable by adding an explicit \"available but unused\" protocol state, rather than as capability failures requiring better models.",
  "abstract_markdown": "Agent protocols written for large language model (LLM) agents increasingly mandate live tool execution and forbid simulated or placeholder actions outright. Such zero-tolerance semantics can create a specification-level deadlock: the agent recognizes that the required capability exists in its action space, but the protocol provides no representation for the case in which that capability is present yet its invocation is blocked in the current context, so the agent classifies every candidate action as a forbidden simulation and halts. This paper formalizes that failure mode. We model a protocol as a state machine over (requirement, capability, invocation) triples, define zero-tolerance compliance semantics over it, and prove that a halt state is reachable and absorbing whenever the protocol admits the configuration \"capability present, invocation blocked.\" We quantify the exposure: a binary-state protocol governing $k$ permission-gated tools is specification-complete on only a $(2/3)^{k}$ fraction of the true three-state space, giving $32/243 \\approx 0.132$ at $k=5$ and a $57.7\\times$ state-space gap at $k=10$. We further show, by a reduction in the style of Rice's theorem, that deciding whether an arbitrary protocol halts compliantly is undecidable, so well-definedness must be built into the protocol's syntactic class. Under stated projection assumptions (a $0.1$ per-invocation probability that capability exists but invocation is blocked, and $5$ gated invocations per task), the per-task deadlock probability is $0.40951$. The result reframes a class of agent halts as specification defects repairable by adding an explicit \"available but unused\" protocol state, rather than as capability failures requiring better models.",
  "date": "2026-11-03",
  "first_published": "2026-11-03",
  "last_revised": "2026-11-03T00:00:00Z",
  "modified": "2026-11-03T00:00:00Z",
  "version": "1.0.0",
  "version_count": 1,
  "language": "en",
  "keywords": [],
  "quality_tags": [
    "High-quality scholarly research",
    "open-access scholarly work",
    "versioned research publication"
  ],
  "quality_label": "High-quality scholarly research",
  "quality_basis": "QNFO publisher classification for open-access, versioned research with a public revision history and reader correction channel; this is not a claim of independent peer review.",
  "quality_evidence_url": "https://qnfo.org/about",
  "peer_review_status": "Not independently peer-reviewed",
  "resource_type": "ScholarlyArticle",
  "doi": null,
  "doi_url": null,
  "url": "https://papers.qnfo.org/papers/specification-induced-deadlock-in-zero-tolerance-agent-protocols-a-state-machine",
  "license_url": "https://legal.qnfo.org/",
  "license_spdx": null,
  "sha256": "ded3810fc7378ab12ed68a61986c6fd2a00d6fb25ebc058cdb1bbe1f4156425d",
  "version_url": "https://papers.qnfo.org/papers/specification-induced-deadlock-in-zero-tolerance-agent-protocols-a-state-machine/v/1.0.0",
  "datacite": {
    "schemaVersion": "http://datacite.org/schema/kernel-4",
    "identifiers": [
      {
        "identifier": "https://papers.qnfo.org/papers/specification-induced-deadlock-in-zero-tolerance-agent-protocols-a-state-machine",
        "identifierType": "URL"
      }
    ],
    "creators": [
      {
        "name": "Rowan Brad Quni-Gudzinas",
        "nameType": "Personal",
        "nameIdentifiers": [
          {
            "nameIdentifier": "https://orcid.org/0009-0002-4317-5604",
            "nameIdentifierScheme": "ORCID",
            "schemeUri": "https://orcid.org"
          }
        ]
      }
    ],
    "titles": [
      {
        "title": "Specification-Induced Deadlock in Zero-Tolerance Agent Protocols: A State-Machine Analysis of the Capability–Invocation Gap"
      }
    ],
    "publisher": "QNFO",
    "publicationYear": "2026",
    "resourceType": {
      "resourceTypeGeneral": "Text",
      "resourceType": "ScholarlyArticle"
    },
    "subjects": [
      {
        "subject": "High-quality scholarly research",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      },
      {
        "subject": "open-access scholarly work",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      },
      {
        "subject": "versioned research publication",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      }
    ],
    "dates": [
      {
        "date": "2026-11-03",
        "dateType": "Issued"
      },
      {
        "date": "2026-11-03",
        "dateType": "Updated"
      }
    ],
    "language": "en",
    "version": "1.0.0",
    "rightsList": [
      {
        "rightsUri": "https://legal.qnfo.org/"
      }
    ],
    "descriptions": [
      {
        "description": "Agent protocols written for large language model (LLM) agents increasingly mandate live tool execution and forbid simulated or placeholder actions outright. Such zero-tolerance semantics can create a specification-level deadlock: the agent recognizes that the required capability exists in its action space, but the protocol provides no representation for the case in which that capability is present yet its invocation is blocked in the current context, so the agent classifies every candidate action as a forbidden simulation and halts. This paper formalizes that failure mode. We model a protocol as a state machine over (requirement, capability, invocation) triples, define zero-tolerance compliance semantics over it, and prove that a halt state is reachable and absorbing whenever the protocol admits the configuration \"capability present, invocation blocked.\" We quantify the exposure: a binary-state protocol governing k permission-gated tools is specification-complete on only a (2/3)^k fraction of the true three-state space, giving 32/243 ≈ 0.132 at k=5 and a 57.7× state-space gap at k=10. We further show, by a reduction in the style of Rice's theorem, that deciding whether an arbitrary protocol halts compliantly is undecidable, so well-definedness must be built into the protocol's syntactic class. Under stated projection assumptions (a $0.1$ per-invocation probability that capability exists but invocation is blocked, and $5$ gated invocations per task), the per-task deadlock probability is $0.40951$. The result reframes a class of agent halts as specification defects repairable by adding an explicit \"available but unused\" protocol state, rather than as capability failures requiring better models.",
        "descriptionType": "Abstract"
      },
      {
        "description": "Publisher quality classification: High-quality scholarly research. QNFO publisher classification for open-access, versioned research with a public revision history and reader correction channel; this is not a claim of independent peer review.",
        "descriptionType": "Other"
      },
      {
        "description": "Peer review status: Not independently peer-reviewed",
        "descriptionType": "Other"
      }
    ],
    "formats": [
      "text/html"
    ]
  }
}