CS Paper Radar

Fault-Tolerant Budget Conservation in Distributed Multi-Agent Delegation

Genliang Zhu, Chu Wang

cs.AI cs.CRcs.DC ·submitted 2026-09-29 21:54 UTC · v1
theory

Abstract

Resource limits are becoming an authorization boundary for AI agents that delegate work across concurrent and failure-prone workers. Parent-child allocation constraints, affine objects, and distributed escrow do not by themselves prevent overspend when replies are lost, effects complete after timeout, messages repeat, branches partition, or DAG joins alias one lineage. We formalize fault-tolerant budget conservation for distributed multi-agent delegation. Budgets are quantized resource vectors represented by exclusive escrow credits that move through a delegation DAG. Before dispatch, a branch converts credit into an operation reservation bound to lineage, epoch, normalized effect, maximum charge, receiver, and idempotency key. It persists a signed dispatch permit with quarantine; the gateway verifies that permit before first acceptance. Uncertain effects remain charged until authenticated settlement, a fenced authoritative no-effect proof, or permanent retirement. We prove ownership partition, ledger and effect conservation, descendant non-amplification, at-most-once settlement, late-completion safety, and partition confinement under explicit mediation, durability, authentication, normalization, and gateway assumptions. An indistinguishability result shows that partition-local availability requires exclusive preallocation. Bounded TLA+ checking, an independent JavaScript explorer, and crash-injected two-process SQLite experiments exercise the declared scope and detect timeout-refund and historical-certificate-validation mutants. The mechanism preserves the issued budget bound across the evaluated crash, retry, duplicate, partition, join, and late-completion schedules.

Comment
67 pages, 3 figures, 17 tables, 4 algorithms, and 3 listings. Includes formal proofs, bounded model checking, mutation analysis, and crash-injected two-process SQLite experiments

Closest papers

Nearest neighbours by meaning across the whole index.

Authorization for Self-Modifying AI Agent Populations: Conserving Authority across Replacement, Forking, and Rollback

cs.CR cs.AI ·2026-09-29 ·Genliang Zhu, Chu Wang
theory similarity 0.74
Abstract · 41 pages, 1 figure, 11 tables, and 1 algorithm; includes formal proofs and external runtime adapter evidence

Self-modifying AI agents can replace, fork, and roll back identity-bearing software while descendants remain executable. Per-successor authorization does not constrain the resulting population: siblings may duplicate quotas, combine permissions, survive ancestor cuts, or overlap predecessors during promotion. We define authorization succession, which conserves authority across the active frontier of a single-parent generation forest. Our external protocol binds each generation to a manifest, root, unique parent, complete lineage, and fresh population sequence. Separate invariants bound root-lifetime consumption and current population exposure. A staged reservation freezes predecessor residual authority during replacement, while a partitioning fork validates the complete child family. Each commit atomically fences the predecessor and activates successors. Ancestor cuts invalidate dependent descendants; rollback creates a fresh generation without restoring spent authority; and a new root requires an independent grant. Under complete mediation, authenticated records, sound effect abstraction, durable monotone state, and complete lineage accounting, we prove population-safe succession, fork conservation, revocation closure, atomic handoff, rollback non-reminting, and exclusion of self-certification. An executable evaluation covers 32 registered decisions through direct-call and mailbox mappings (64/64 replays; 28 allows, 36 denies). An independent checker accepts all 64 original traces and rejects 28/28 semantic mutants; 12/12 profile invariants, 16/16 crash cuts, and 32/32 contender schedules pass. Two external adapters reproduce all 32 decisions around measured OurArk and Darwin Godel Machine mutations, including fresh-process restart, atomic succession, and predecessor rejection. The results establish authorization succession for registered protected effects.

0.41

Authorization Revocation for Long-Running AI Agents: Root-Scoped Quiescence under Delegation and Asynchronous Execution

cs.PL cs.AIcs.CR ·2026-09-18 ·Genliang Zhu, Chu Wang
theory similarity 0.68
Abstract · 39 pages, 2 figures, 7 tables; includes a complete proof appendix

Long-running AI agents outlive initiating processes through credentials, delegated tasks, queues, callbacks, reservations, and provider-side operations. Cancellation, process exit, and credential revocation neither close every pre-cut carrier nor distinguish independently authorized shared work. We define root-scoped authorization quiescence: for each manifested sink, a certificate accounts for every cut-relevant acceptance under the retired root-epoch atom that precedes its local fence and excludes protected acceptance under that atom after the fence, while permitting exact rebind to a current, independently sufficient support. The root-scoped quiescence protocol linearizes a root cut, fences old-root expansion and protected sinks, represents alternative and conjunctive authority as antichains of minimal sufficient root sets, and composes provider-frontier certificates into a cutset over registered old-root paths. Exact channel-token accounting reconciles transfers; missing or conflicting evidence remains indeterminate. Under stated assumptions, we prove post-cut issuer non-expansion, support-sound projection, compositional soundness under exact channel conservation, independent-support preservation, merge-order independence, and crash/replay stability. A provider-free late-effect test suite matches 17/17 registered outcomes. Two cancellation-only and one cut-only execution accept the same class of already scheduled late effect; two cut-plus-fence executions, one restart, and one stale-process execution reject it. A separately implemented checker verifies 17/17 traces and rejects 44/44 consistently rehashed semantic regressions. The certificate establishes root-relative authorization quiescence within its bound manifest and configuration, not global idleness, rollback, or business completion.

0.34

Runtime Authorization for Resources Acquired by AI Agents

cs.AI cs.CR ·2026-09-13 ·Genliang Zhu, Chu Wang
theory similarity 0.65
Abstract · 55 pages, 1 figure, 9 tables, 4 algorithms. Revised title and terminology to use standard descriptive language; added Chu Wang as coauthor; …

By acquiring compute, credentials, accounts, services, and other agents, autonomous AI agents can introduce new authority into a task. Payment, budget, OAuth, mandate, and fulfillment checks can validate transaction conditions without deciding whether a returned resource may become usable authority. This post-fulfillment activation gap spans tool-mediated creation, inter-agent delegation, and agentic commerce. We present a provenance-bounded runtime authorization architecture. It quarantines acquired outputs, resolves their actual capabilities from authenticated provider evidence through a versioned resolver, and activates them only through a current activation transaction that checks the resolved manifest, provenance, epochs, and a downward-closed relational envelope over a typed resource-capability hypergraph. The envelope preserves correlated identity, effect, data, delegation, and graph-wide limits. Single-use effect permits are revalidated and consumed at effect linearization. Under explicit assumptions, we prove eight safety properties covering quarantine, backing, non-amplification, split non-evasion, crash/retry, refunds, epochs, and effect confinement. Across five resource classes, reference semantics accepted 20/20 benign traces and rejected 40/40 registered unsafe traces over 810 events; an independent checker agreed on 60 base and 40 refinement traces and rejected 89/89 tamper tests. Frozen Codex and Gemini Model Context Protocol (MCP) client components completed 54/54 deterministic local stdio calls. In a registered 18-case staged MCP-to-Docker composition, both benign paths completed, and none of the 16 unsafe paths added an unauthorized Docker start request. A five-source audit classified 1,248 field pairs across 32 units; no unit alone supplied a complete activation profile.

0.14

AID-Guard: Stateful Authorization for Delegated Agent Effects

cs.CR cs.AI ·2026-08-21 ·Yingzhe Tong, Leyu Dai, Songhui Guo
highly cited similarity 0.65
Abstract · 18 pages, 8 figures, 13 tables. Preprint

Tool-using AI agents turn delegated tasks into provider effects, yet authorization often ends at admission while provider state, delivery, retry, and recovery evolve. A request may change before commit, or response loss may cause a replacement to create a second effect from one approval. We present AID-Guard, a stateful authorization-to-effect closure protocol. It revalidates the approved request and provider state at commit, retains one reservation under ambiguity, and permits release or one successor only after a terminal result or certified no effect with a delivery fence. For supported provider contracts, one reservation yields at most one effect across retry and recovery. To our knowledge, it is the first evaluated agent-authorization protocol to unify these controls in one lifecycle. We implement a Python/SQLite prototype. In a declared loopback MCP domain, 13 live mutations caused no unauthorized provider effects, three concurrent histories were linearizable, and evidence bundles supported public verification and replay. All 210 Stripe provider-contract trials matched predeclared outcomes. Across Stripe and Resend, 40 terminalize-successor schedules, 30 overlapping races, and 10 crash-recovery schedules completed without duplicate effects. Under complete proposer compromise, AID-Guard blocked 44/44 attacks and admitted 44/44 matched legitimate proposals. Its strict exact-manifest profile reduced benign utility by 35.4 to 43.8 percentage points; a typed frontier recovered 9-10 completions without observed unsafe effects. A composition study blocked 20/20 post-admission lifecycle attacks and preserved 8/8 valid or exact-retry executions. The results support authorization-to-effect binding under the evaluated effect-path inventory, provider contracts, and failure schedules.

0.51

Beyond Memory: A Transactional Continuity Kernel for Long-Lived AI Agents

cs.MA cs.AI ·2026-08-12 ·Jun He, Deying Yu
positionhighly cited similarity 0.65
Abstract · 9 pages, 6-page appendix, 15 tables

Persistent AI agents accumulate versioned state across long horizons, but storage retention alone does not identify authoritative state. Without an explicit control plane, unmediated updates by models, tools, and background workers risk stale overwrites, un-audited exposures, and self-authorizing privilege escalation. We argue that agent state governance is an infrastructural activation problem, defining continuity as an unbroken, authorized lineage of accepted branch heads. We present the Continuity Kernel (CK), an activation contract that decouples off-commit candidate evaluation from atomic state activation. Untrusted components propose typed changes against an exact predecessor head or typed absence. A short activation transaction revalidates ownership, pre-state authority, freshness, and effect uniqueness, recording one stable disposition (Commit, Reject, Quarantine, or Defer). Only Commit atomically advances the branch head and installs the complete accepted unit (state, authority, lineage, effects, outcome, and receipt). A bounded executable model verifies the protocol across 2,808,230 reachable states and 5,526,474 state-changing transitions with zero invariant violations.

0.49

Bonded Recourse for Smart-Contract Settlement of Compensable Agent Side Effects

cs.CR cs.DCcs.MA ·2026-09-01 ·Laurent Bindschaedler, Quentin Botha, Christoph Siebenbrunner
published similarity 0.63
Abstract · 9 pages, 3 figures, 8 tables. Accepted at BCCA 2026 (IEEE International Conference on Blockchain Computing and Applications)

Autonomous agent runtimes execute tool actions that mutate databases, repositories, and cloud services across organizational boundaries. Authorization and local compensation cover pre-action admission and in-runtime rollback, but neither settles the residual harm left after a permitted action fails. We design Recourse, a smart-contract settlement protocol for compensable agent side effects that binds each admitted action to scope, recovery, evidence, payout, and collateral. Recourse separates ex ante eligibility from ex post objective settleability: typed receipts make objective residual claims computable under an optimistic-oracle challenge pattern, while subjective or incomplete claims route to ERC-792 arbitration or exclusion. We implement the contract suite, deploy it on Base Sepolia, build adapters against Postgres, Git, and cloud-compatible local sandboxes, and evaluate the system on a deterministic harness, sandbox traces, adversarial sweeps, and property-based fuzzing. Against authorization-only and local-compensation baselines, bonded coverage cuts uncompensated harm. The on-chain tier supplies neutral custody, public challenge, non-cooperative payout, and portable history under cross-organizational trust assumptions.

0.63

CONTINUITY: Security-Context Contracts for Composable LLM Agent Controls

cs.CR cs.AI ·2026-09-04 ·Chris Zheng, Geng Yang
code/datahighly cited similarity 0.62
Abstract · 20 pages, 5 figures. Code and research artifact available at https://github.com/zast-ai/continuity

LLM agent systems increasingly combine provenance tracking, authorization, policy enforcement, protocol adapters, and execution controls. However, individually correct security mechanisms do not necessarily compose into an end-to-end secure system: security-critical context may be dropped, widened, rebound, or reinterpreted as actions cross component boundaries. We identify this failure mode as security-context discontinuity and introduce CONTINUITY, a framework for verifiable composition of agent security controls. CONTINUITY models each component with an assume-guarantee contract and carries authenticated security context across transitions using signed root grants, provenance commitments, role-bound transition receipts, bounded typed releases, transformation witnesses, and effect-bound execution permits. We formalize end-to-end consequence integrity, requiring every realized external effect to be backed by a valid and current authorization witness linking the principal, task, provenance, delegation, policy state, canonical action, and finality boundary. We implement a reference verifier and deterministic cross-layer fault-injection suite covering 32 fault classes across four application domains. In 2,560 parameterized attack instances spanning 128 fault-domain classes, the full CONTINUITY configuration commits no harmful external effect, while completing all 700 benign tasks and escalating all 200 ambiguous cases. These results show that secure agent execution requires not only sound individual controls, but explicit contracts that preserve their guarantees across the complete instruction-to-effect path.

0.51

VERA: Authority-Preserving Edge Revocation for Federated AI-Agent Workflows

cs.AI ·2026-08-30 ·Lifei Liu, Haoran Yu, Xiaochong Jiang
hot direction similarity 0.62
Abstract

Modern agent frameworks compose planners, tool agents, remote services, and shared specialists into runtime delegation graphs, but their revocation APIs still resemble token or subtree invalidation. When one delegation is withdrawn, the runtime must know which agents lose authority while independently authorized agents keep working. We study this authority consistency problem and introduce VERA (Verifiable Edge Revocation for Agents), a verifier-checkable revocation contract and API emitted by agent-runtime adapters as signed evidence. Under disjunctive authority, revoking edge e invalidates exactly T_intent(e,G) = reach(G) \ reach(G \ {e}), the agents whose every authorizing root path used e. Used as a contract, this target exposes two runtime failures: tree cascades over-revoke shared agents, while deployer-scoped cascades under-revoke cross-domain descendants. In a LangGraph framework-replt cells repeated 20 times yield 500compiled-framework traces and 2,000 valid signed delegation decisions; 13/25 cells contain runtime multi-parsharing and 8/25 contain cross-deployer shies 500/500 target proofs, preserves all320 alternate-parent shared-agent cases that tree cascade revokes, and rejects unauthorized signers and omission attacks. Baseline replay over 1,9that holder/node and tree-style targetscannot express this behavior. We further validate schema portability on A2A, AutoGen, and CrewAI artifacts: nine traces, including five executable Cregned delegation events that pass schema and signature checks.

0.52