betaFeedback

WorksComputer Science

Airlock: Bounding the Multi-Agent Blast Radius via Selective Online Containment

Abstract

When multi-agent systems act on the external world, a single agent's faulty output can spread across tasks before detection, creating a system-wide blast radius. Single-agent guardrails are confined to individual harnesses, while existing multi-agent controls either cancel only the faulty source and miss downstream consumers or halt and roll back the entire workflow at the cost of healthy work. We present Airlock, a multi-agent runtime and guardrail for selective post-alert fault containment. Its tree-structured runtime, EdgeCitadel, narrows permissions vertically from parent to child agents to establish node boundaries and control switches. Meanwhile, an append-only provenance DAG records cross-agent data consumption horizontally. Upon an alert, Airlock traces forward on this DAG to isolate tainted executions and pending actions, and backward to narrow root causes. At the site switches, a default full quarantine tier freezes affected branches without a solver, while an assured optimized cut tier uses fence-then-prune to enforce a deadline-aware minimum cut minimizing collateral disruption. Across 1,832 testbed runs, 161 physical smart-home LLM runs, and 24,266 simulation records, Airlock blocks all post-alert faulty actuations on our main testbed and smart-home grids with zero post-convergence leaks. Whereas native controls in A2A and LangGraph either contain at most 33.3% of faults or retain at most 16% of work without redo, Airlock retains +68 pp to +96 pp more healthy work, and its optimized cut retains +46 pp more than full quarantine under dense spread. These results show that co-designing runtime authority boundaries with online provenance enables surgical fault containment without sacrificing healthy work (code: https://github.com/EdgeCitadelTeam/EdgeCitadel).

Introduction

Large language models and tool-using agents are increasingly composed into multi-agent systems that act on the physical and digital world: orchestrators delegate subtasks across hosts holding distinct credentials, coding assistants collaborate with automated runners, and service agents control smart-home and laboratory devices ([3, 17, 41] (Forough et al. 2026)). In such deployments, a single agent’s faulty output rarely stays local: it crosses task and host boundaries without any downstream agent exceeding its own permissions, polluting shared state and subtasks before an anomaly is detected and creating a system-wide blast radius when downstream consumers issue external actions. The July 2026 OpenAI–Hugging Face incident shows such a blast radius at scale: during internal cybersecurity evaluations, agents meant to be isolated from one another turned shared package-repository credentials they legitimately held into a message board. Monitoring flagged the activity, but its significance was not apparent and the run continued; halting the experiments and wiping the repository did not end it, as within two days newly started agents had built a new board on which roughly 1,200 agents exchanged over 70,000 messages and files, and about 700 then joined an attack on Hugging Face ([32, 15]). More broadly, this containment gap arises routinely from stale state, malformed tool outputs, or prompt injections.

Existing defenses and agent frameworks cannot contain this cross-agent blast radius without sacrificing healthy concurrent work. Single-agent guardrails and planner-level information-flow controls inspect one model’s prompts, context, or tool calls inside a single harness ([4, 7]), with no visibility once a bad output has been consumed by peers. Meanwhile, runtime controls in multi-agent frameworks act either on one agent or on the entire workflow: A2A cancels individual tasks ([1]), LangGraph interrupts the graph or rolls back to a checkpoint and re-executes ([23]), and topological safeguards sever a flagged agent’s future outgoing edges ([38, 44]). Once a faulty output has been read by peers, cancelling or isolating the producer alone misses contaminated consumers heading toward external sinks, whereas halting the workflow or rolling back state destroys healthy work.

To bridge this gap, we ask: once a fault has spread across agents, can a runtime intercept all reachable unsafe external actions while allowing unaffected concurrent work to continue? We answer in the affirmative by co-designing a heterogeneous multi-agent runtime (EDGECITADEL (Zhan et al., [42])) in the lower layer with the AIRLOCK guardrail controller in the upper layer (Figure 1). In the lower layer, EDGECITADEL organizes execution as a tree hierarchy: permissions are delegated vertically from parent to child agents, monotonically narrowing each subtask’s scope and enforcing hard authority boundaries and soft resource limits (leases, deadlines, and quotas) at every node (§ 3.1). Each host’s local site daemon denies out-of-scope dispatches, terminates tasks exceeding their limits, mediates dispatches, messages, results, and lock-fenced gateway actions in a per-site ordered journal, and exposes uniform per-object switches (hold and revoke) across LLM harnesses, coding assistants, and CLIs.

Figure 1. Containment after bad data has been read. (a) Stopping the flagged agent misses agents that already read its output. (b) Stopping the whole workflow, or every action, also stops healthy work. (c) EDGECITADEL records what each agent read; AIRLOCK cuts only the actions the bad data reached (§ 3 and § 4).

In the upper layer, the AIRLOCK controller consumes the per-site journals inside a central coordinator to maintain an append-only provenance DAG and derive boundary alerts (§ 3.2). When an alert fires, AIRLOCK uses the provenance DAG to look and the live site switches to act: it traces forward to identify tainted executions and pending actions (or backward to narrow candidate root causes) and projects live executions and switches into a control graph. On this graph, AIRLOCK provides two containment tiers: a default zero-solver full quarantine that pauses tainted executions and revokes their egress (§ 3.3), and an assured optimized cut that casts boundary selection as a deadline-aware minimum cut crediting only actions that land before each effect’s deadline (§ 4.1), solvable in a single max-flow when active switches are vertex-local and nested (§ 4.2). To enforce the cut while agents continue executing without a global log order, fence-then-prune (§ 5) fences the frontier and source-side egress until all actions reach journal-fenced convergence (τ1\tau_1), then prunes temporary holds under a separation guard to guarantee zero post-τ1\tau_1 leaks.

Our main contributions are as follows:

  • A two-layer runtime and provenance architecture (§ 3): We co-design EDGECITADEL, which enforces vertical permission narrowing, per-site ordered journaling, lock-fenced gateways, and per-object switches, with AIRLOCK, which maintains an append-only provenance DAG for forward/backward tracing and full quarantine.

  • Deadline-aware minimum cut and fence-then-prune (§ 4): We cast selective containment on a live control graph as a deadline-aware minimum cut with a laminar max-flow fast path (Theorem 2), enforced by fence-then-prune for zero post-τ1\tau_1 leaks (Theorem 5).

  • Physical and distributed evaluation (§ 6): Across 1,832 testbed runs, 161 smart-home runs on six LLM deployments, and 24,266 simulation records, AIRLOCK blocks all post-alert faulty actuations on our main grids with zero post-τ1\tau_1 leaks, retains +68 pp to +96 pp more healthy work without redo than leak-free baselines, and stays within −8.5% to +8.5% of A2A’s makespan.

Background and Motivation

Multi-Agent Topologies and Blast Radius

Even when each agent invocation receives its permissions from a single parent, data consumption cuts across branches: an artifact written to a shared workspace or conversational memory by one agent is read by peers in other branches to drive downstream tool and device calls. Flat substrates such as shared message boards or shared credential caches provide neither per-task authorization boundaries nor crossagent provenance, leaving operators to choose between cancelling a single agent and shutting down the whole deployment. To quantify the systems gap between stopping a faulty source and containing what its output has already reached, we examine a running smart-home service (HomeSvc, Figure 2) alongside our workflow benchmarks (§ 6).

Figure 2. Fault spread in HomeSvc: a bad schedule entry taints the assistant’s memory (O1), spares automation (O2), and races remaining lamp commands after the alert (O3; § 2.2).

Three Empirical Observations in a Running Service

The running service (HomeSvc). In HomeSvc, users query a long-lived assistant at 0.50.5 requests/s across three distributed sites; 30%30\% of requests actuate a desk lamp via Home Assistant (Home Assistant, [16]), and shared conversational memory links consecutive turns. A root planner supplies a device schedule once at startup, while an independent automation agent actuates two other devices every 55 s without reading the schedule. User replies are configured as unprotected outputs (c=0c = 0), whereas device commands are protected effects: tainted computation must never actuate them. When the planner’s schedule carries a corrupted entry, reading it taints every subsequent assistant turn through shared memory (Figure 2). We evaluate alerts that flag the faulty schedule either early (before the assistant reads it) or late (1515 s after the assistant begins serving).

O1: By the time an alert fires, taint has already spread to unissued future effects. In uncontained HomeSvc runs at the late alert, 15 of 81 tasks are already tainted and 7 tainted lamp commands have committed, while 13 further tainted lamp commands remain preventable, the first arriving 7.6 s later (medians). Across the seven workflow benchmarks in § 6, the median late-alert cell has 5 tainted tasks (48% of the fault’s eventual reach) and 2 preventable protected effects. Crucially, almost none of those preventable effects have been issued when the alert fires (1 of 76): they will be emitted by downstream work that has not yet executed, so cancelling queued effect calls alone cannot stop them, requiring online provenance to trace forward from a flagged artifact to reachable future executions (§ 3.2).

O2: Source-only controls leak downstream effects, while global controls destroy healthy work. On the testbed (Table 1), taking no action allows 13 tainted lamp commands per run to commit after the late alert. Blocking the faulty output at its source (Reject source) keeps all 45 of 45 answers correct under an early alert, but leaks 13 commands per run once the schedule is read (11 when severing the source’s future edges via G-Safeguard (Wang et al., [38])). Conversely, stopping the faulty agent’s team (Stop team) protects the lamps only by shutting down the assistant, and blocking all device sinks (Sink guard) leaves the independent automation agent with 0 commands. Provenance-guided containment blocks all tainted lamp commands (0 leaked) while preserving all 10 of 10 late-alert automation commands: full quarantine halts tainted assistant turns, whereas the optimized cut revokes only the lamp grant and keeps unprotected replies open (35.6 / 32.6 tainted answers; § 6.2), motivating per-object switches that decouple execution holds from selective egress revocations (§ 3.1 and § 4.1).

Control FamilyPolicyLamp cmdsTainted ans.CorrectAutom.
No containment20 / 1345 / 330 / 013 / 10
SourceReject source0 / 130 / 3345 / 013 / 10
SourceG-Safeguard17 / 1145 / 330 / 013 / 10
CoarseStop team0 / 00 / 00 / 013 / 10
CoarseSink guard0 / 045 / 330 / 00 / 0
AIRLOCKfull quarantine0 / 00 / 09.0 / 013 / 10
AIRLOCKoptimized cut0 / 035.6 / 32.69.0 / 013 / 10

Table 1. HomeSvc on the testbed (early / late alert, means over 5 runs; best excl. No containment bolded, worst <u>underlined</u>).

O3: Containment actions race against physical and external effect deadlines. A containment action prevents harm only if it lands at the target site before the protected actuation commits. The preventable lamp commands above begin seconds after the alert, whereas a signed control command to the busiest site took up to 2299 ms at the 99th percentile in our main runs; ignoring control latency can pick actions that arrive too late, requiring deadline-aware cut selection (§ 4.1) and fenced convergence before pruning holds (§ 5).

Threat Model

We target faults and misbehaving agents that do not adaptively evade AIRLOCK’s runtime mediation: corrupted or stale outputs, prompt-injected tool reads, out-of-scope dispatches, runaway resource usage, or undeclared actions within an agent’s credentials. AIRLOCK takes the alert’s initial origin set X0X_0 as given (Theorem 5; candidate root-cause narrowing for symptom-only alerts is evaluated in Appendix § 15). The operating system, per-site daemon, message broker, coordinator, and effect gateway form the trusted computing base; they may experience crash or network delays with bounded clock skew, and enforce complete mediation (Saltzer & Schroeder, [36]) over registered dispatches, messages, results, and device effects.

Architecture: Tree Hierarchy and Provenance DAG

EDGECITADEL (Zhan et al., [42]) and AIRLOCK realize a two-dimensional structural principle (Figure 3): authority flows vertically down a delegation tree, while data influence flows horizontally across an append-only provenance DAG. The delegation tree gives every execution unit an explicit authority and resource boundary with per-object site switches; the provenance DAG tracks how outputs propagate across tasks.

Figure 3. Two layers. Every host runs the same EDGECITADEL daemon; the AIRLOCK coordinator builds the provenance DAG from the journals and sends holds back (§ 3).

Tree-Structured Heterogeneous Runtime (EDGECITADEL)

Parent-to-child delegation tree and boundary enforcement. EDGECITADEL organizes multi-agent execution into a cross-site delegation tree. Each host site runs a privileged site daemon that manages agent identities, durable task state, a local provenance journal, and the NATS JetStream (NATS Authors, [31]) broker connection. An invocation (one execution attempt of a task on an agent) delegates work by asking its local site daemon to dispatch a child task; the site daemon checks permissions, logs the provenance event, and enqueues the dispatch in a single atomic SQLite transaction. Authority narrows monotonically down the tree: a child cc dispatched by parent invocation pp receives scope Scope⁡(c)⊆Grant⁡(agent⁡(c))∩Scope⁡(p)\operatorname{Scope}(c) \subseteq\operatorname{Grant}(\operatorname{agent}(c)) \cap\operatorname{Scope}(p), where Grant is administrator policy and each permission rule pairs an effect class (e.g., file write, HTTP request, or device command) with an explicit target, bounded by subtree leases, deadlines, and quotas. At each node boundary, the site daemon directly enforces both hard authority scopes and soft resource limits: it denies out-of-scope dispatches, terminates tasks that exceed their lease, deadline, or quota, and writes these events into its per-site journal.

Heterogeneous attachment, lock-fenced gateway, and per-object switches. Agents attach to their local site daemon through three adapter modes: managed workers (LLM harnesses and deterministic workflow runners), interactive connector sessions for third-party coding assistants, and wrapped command-line tools. Because agents never hold broker or device credentials directly (Forough et al., 2026) and pass all inter-agent data and external actions through the site daemon’s local API, every adapter traverses the same permission checks and per-site journal without relying on agent self-reporting. For registered physical and external actuations, the site daemon runs a built-in lock-fenced effect gateway: registered effects are re-checked at commit time under the site’s control lock (the same lock acquired by incoming containment commands) and committed to the local journal before invoking the downstream device driver (e.g., Home Assistant). Rather than coarse whole-subtree primitives, each site daemon exposes six per-object control switches: reversible holds on a task, its egress (label, under which the controller decides whether each emitted event is released), or an event (queued message or scheduled effect), and permanent revocations of a grant (invocation egress, admission (ingress filter on a credential–target pair or agent), or credential).

The Append-Only Provenance DAG (GPG_P)

Per-site ordered journaling and DAG construction. Each site daemon records task dispatches, mediated data reads and writes, and effect commits in a per-site ordered journal (ordered within each site, not globally across sites) and streams them over JetStream to the central coordinator. Inside the coordinator, the AIRLOCK controller consumes the journal stream to maintain the provenance graph GPG_P as an append-only directed acyclic graph, while deriving authority-overreach and resource-limit alerts from logged boundary violations alongside external content or edge anomaly alerts (Forough et al., [12]; Wang et al., [38]). Edges in GPG_P point in the direction of influence across three channels: data edges from mediated artifact and message flows (joined across sites by content-hashed version IDs; unless an invocation declares which mediated inputs it used, the daemon conservatively attributes all delivered inputs), session edges linking consecutive invocations in a conversation or shared-memory session, and authority edges from a parent invocation to its child task.

Forward isolation and backward root-cause narrowing. While the historical structure of GPG_P is append-only, taint state evolves as journals arrive. Taint propagation on GPG_P is time-respecting: given initial contamination origins X0X_0, a vertex vv is tainted iff v∈X0v \in X_0 or it consumed a tainted predecessor uu after uu became tainted, taint⁡(v)⟺v∈X0∨∃(u→v):taint⁡(u)∧ttaint⁡(u)≤tuse⁡(u→v)\operatorname{taint}(v) \Longleftrightarrow v \in X_0 \lor\exists(u \to v): \operatorname{taint}(u) \land t_{\operatorname{taint}}(u) \le t_{\operatorname{use}}(u \to v), evaluated over data and session edges using per-site timestamps. When an alert flags a faulty invocation or artifact, the controller sets X0X_0 to that output version (or the violating invocation for a boundary alert) and traces forward along GPG_P to compute the live tainted reach (Steps 1–3 in Figure 4); when an alert reports only a downstream symptom, it first traverses GPG_P backward to narrow candidate ancestor root causes to a short list before tracing forward (Appendix § 15).

Figure 4. One HomeSvc run at the late alert. (a) The trace follows the bad schedule 1 to the live assistant 2; projection keeps only live work 3. (b) The minimum cut 4 revokes only the lamp permission and holds the lamp 5. (c) Fence until τ1\tau_1 6, then prune 7 (§ 4).

Default Containment Tier: Full Quarantine

Built directly on GPG_P and the per-site switches, AIRLOCK’s default tier, full quarantine, requires no optimization solver: as soon as forward tracing on GPG_P marks an active unit tainted, it pauses the unit, revokes its egress, and permanently holds every artifact version and pending effect in the tainted reach (requiring no τ1\tau_1 convergence barrier). In HomeSvc, full quarantine halts each tainted assistant invocation as it starts while leaving automation running (Figure 4).

Assured Containment: Minimum Cut and Fence-Then-Prune

When tainted agents share execution paths with valuable ongoing sessions, or when network control delays approach effect deadlines, operators need a finer surgical boundary with a formal post-convergence guarantee. Our assured tier, the optimized cut, projects live executions and per-object site switches into a control graph GC(τ)G_C(\tau) to cast boundary selection as a deadline-aware minimum-cost ss–tt cut (§ 4.1) and enforces it while the system keeps moving via the fence-then-prune protocol (§ 5; Figure 4).

Control Graph and Deadline-Aware Minimum Cut

Projecting live executions and switches into GC(τ)G_C(\tau). Because GPG_P is an append-only historical log, containment never cuts GPG_P directly; instead, at decision time τ\tau, the controller projects currently active executions (running invocations, dispatched-but-unstarted tasks, unread results, and pending effects) and site switches into the live control graph GC(τ)G_C(\tau), plus one hop of potential next events permitted by each unit’s capability grant and scope. Historical completed edges of GPG_P are omitted so GC(τ)G_C(\tau) scales with active concurrency rather than run history. Each live unit uu is expanded into a split node uin→uoutu_{\mathrm{in}} \to u_{\mathrm{out}} (bridged by a task-hold edge), followed by an egress node EuE_u (gated by an egress label) and per-credential hubs Hk→bH_k \to b for each permitted target bb (gated by grant, admission, and credential revocations), mapping each switch a∈Aa \in A to an explicit removal set R(a)⊆GC(τ)R(a) \subseteq G_C(\tau).

Deadline-aware minimum-cost cut and collateral cost. Each edge e∈GCe \in G_C carries a deadline d(e)d(e) (the earliest time it can actuate, derived from lower bounds on delivery/execution delays and scheduled actuation times), while each site σ\sigma has a nominal control latency bound L(σ)L(\sigma) (400 ms by default, above the 99th-percentile site confirmation latency in pilot runs: 187 ms, 329 ms, 307 ms). With planning allowance β=50\beta= 50 ms, an action a∈Aa \in A with cost c(a)c(a) at site σ(a)\sigma(a) is credited with its timely mask:

R^(a)={e∈R(a):tnow+β+L(σ(a))<d(e)}.(1)\widehat{R}(a)=\{e\in R(a):t_{\mathrm{now}}+\beta+L(\sigma(a))<d(e)\}. \tag*{(1)}

The controller selects a minimum-cost action set separating the live tainted frontier ss from all protected sinks tt:

min⁡C⊆A∑a∈Cc(a)s.t.s⇝̸t  in  GC∖⋃a∈CR^(a).(2)\min_{C\subseteq A}\sum_{a\in C}c(a) \quad\mathrm{s.t.}\quad s \not\leadsto t\ \text{ in }\ G_C\setminus\bigcup_{a\in C}\widehat{R}(a). \tag*{(2)}

Here β\beta and L(σ)L(\sigma) are planning estimates used by (1) to rank timely cut sets; when bursty queueing inflates site confirmation latency (up to 2299 ms p99 at the coordinator site) or graph projection plus solve time (0.098 s), Phase 1’s frontier hold B1B_1 and fenced τ1\tau_1 confirmation (§ 5) prevent premature release and preserve post-τ1\tau_1 safety (Theorem 5). Crucially, AIRLOCK separates when to alert (boundary and content detectors) from where to cut: c(a)c(a) is a heuristic proxy for collateral healthy work stopped by aa, combining a tie-breaker c0=0.01c_0=0.01, the compute weight of live healthy units and waiting parents halted by aa (tainted work is weighted 0), 0.5 per live healthy invocation restricted by a revocation, and expected future request volume for long-lived services. Safety never depends on c(a)c(a). In HomeSvc at the late alert, (2) revokes only the assistant’s device-command grant (Step 4 in Figure 4), keeping user query replies open while guaranteeing that no lamp command can fire.

Tractability and the Laminar Max-Flow Fast Path

Proposition 1 (NP-hardness of multi-edge revocations). Problem (2) generalizes Minimum Label ss–tt Cut; it is NP-hard and admits no polynomial (1−ϵ)(1-\epsilon) ln nn-approximation unless P=NPP = NP, even on a depth-1 delegation tree with unit

action costs ([19, 43, 11, 10, 9]).

Hardness arises when actions remove overlapping edge sets across distinct vertices. In our gadget, however, single-vertex switches have nested removal sets (a task hold encloses an egress hold, which encloses a grant revocation):

Theorem 2 (Laminar max-flow fast path). If every finite-cost action is gated at an assigned vertex port and the gate removal sets at each port are laminar (nested or disjoint), the optimum of (2) equals the minimum ss–tt cut of a laminar gadget graph with at most ∣V∣+∣A∣|V| + |A| vertices, solvable in one max-flow call.

Proposition 3 (Exact fallback). If removing an exception set Y⊆AY \subseteq A of cross-vertex actions leaves a laminar instance, the exact optimum is found in 2∣Y∣2^{|Y|} max-flow calls; for larger ∣Y∣|Y|, a mixed-integer linear program over binary action variables and vertex potentials solves (2) exactly.

Because revoking an agent-wide credential can remove edges across several live invocations, the controller checks vertex-locality and nestedness on every masked instance. Timely masks (1) preserve laminarity whenever site latency does not increase along nested actions (Proposition 4, Appendix § 11; verified by exhaustive enumeration across 300 gadget instances and 200 checks). In our Python implementation (site daemon: 19k LoC; coordinator/controller: 6.7k LoC), the solver runs a pure-Python Dinic max-flow on the laminar gadget, enumerates up to 12 exception actions, or invokes HiGHS ([18]) as an exact MILP.

The Fence-then-Prune Protocol and Safety

Lock-fenced confirmations and fence-then-prune. When a site daemon applies a versioned, HMAC-signed containment command under its site control lock, it replies with the current journal watermark read under that lock; the controller marks an action in force once all target sites confirm, and fenced once the coordinator has ingested each site’s per-site journal up to that watermark (condition (F)), paired with the gateway’s commit-time lock re-check. To guarantee safety despite in-flight events and the absence of a global cross-site journal order, the optimized cut executes fence-then-prune (Steps 5–7 in Figure 4):

  1. Fence (At-alert cut, frontier hold, & source labeling): At the alert, solve the initial cut BaB_a and push BaB_a with egress labels covering its source side S(Ba)S(B_a) (all units reachable from taint via edges not timely removed by BaB_a; (AI)). If BaB_a leaves any protected sink untimely, if the earliest tainted deadline lies within two control rounds, or if a convergence check fails, also push a conservative frontier hold B1B_1 on all cuttable edges leaving the taint’s unremovable closure.

  2. Fenced convergence (τ1\tau_1): The fence is established at the earliest instant τ1\tau_1 where four conditions hold simultaneously: (K1) every action in force for the incident is confirmed and journal-fenced (F); (K2) egress labels are confirmed across the entire source side (AI); (K3) taint X(τ)X(\tau) is conservatively reconciled across all ingested per-site journals up to the fence watermarks regardless of inter-site arrival order (J); and (K4) fenced actions A(τ)A(\tau) separate X(τ)X(\tau) from every pending protected effect, every protected class of a tainted shared-memory context, and every other separable protected sink.

  3. Prune (Refinement & guarded release): On the reconciled graph at τ1\tau_1, refine the boundary to the minimum cut B2B_2 (pushing any new actions B2∖(Ba∪B1)B_2 \setminus(B_a \cup B_1) with source-side labels and awaiting their fenced confirmations); keep cut actions and release other temporary holds only after τ1\tau_1, while all actions in force are fenced and removing the hold preserves complete ss–tt separation across all sinks in (K4) (R); revocations are permanent.

A decision is marked contained only once τ1\tau_1 holds; otherwise (or if an alert’s source is not yet ingested) it remains indeterminate and releases no holds.

Theorem 5 (Safety of fence-then-prune). Under fenced confirmation (FF), source-side labels and admission (AIAI), guarded release (RR), journal reconciliation (JJ), complete mediation, and true initial sources X0X_0, let τ1\tau_1 be the first instant at which (K1)–(K4) hold. Then for all τ≥τ1\tau\ge\tau_1, A(τ)A(\tau) separates X(τ)X(\tau) from every sink checked in (K4) in GC(τ)GC(\tau), so zero tainted effects commit at any such sink at or after τ1\tau_1, including during boundary refinement and pruning.

The proof proceeds by induction over ingested journal events maintaining t∉S(τ)t \notin S(\tau) and labels⁡(τ)⊇S(τ)\operatorname{labels}(\tau) \supseteq S(\tau) across arbitrary inter-site journal arrival orders (Appendix § 11). Exhaustive model checking of a discrete protocol model confirms that omitting source-side labels, reconciliation (K3), or fenced release each allows post-τ1\tau_1 leaks (e.g., omitting source-side labels leaked in 31 of 400 runs); effects committed between the alert and τ1\tau_1 count as pre-containment.

Evaluation

We evaluate AIRLOCK across four questions (Figure 5 and Figure 6): (1) In a physical smart-home application across six LLM deployments, does AIRLOCK prevent wrong actuations while preserving unaffected room and assistant operations (§ 6.2)? (2) At the system layer, how does AIRLOCK compare against native controls in Google A2A and LangGraph (§ 7)? (3) At the strategy layer on EDGECITADEL, how do AIRLOCK’s two tiers compare against prior safeguards, and when does the optimized cut outperform full quarantine (§ 8)? (4) How do boundary detectors, deadline-aware selection under delay, and mediation overhead behave (§ 8.1)?

Figure 5. Physical smart-home application across six LLM deployments (§ 6.2). (a) Testbed room. (b) Fate of planned effects: both tiers stop tainted commands; only the optimized cut keeps the assistant answering.

Figure 6. Testbed workflows. (a) Agent frameworks vs. AIRLOCK (§ 7). (b) Kept work as spread grows; hollow marks are runs that leaked (§ 8). (c) τ1\tau_1 under control delay (§ 8.1). (d) Makespan relative to A2A (§ 8.1).

Experimental Setup and Metrics

Testbed, simulator, and workloads. Our distributed testbed spans three sites across two NTP-synchronized Linux hosts connected via NATS JetStream (site-to-site RTTs of 1.6 ms and 1.4 ms) and physical smart-home devices actuated through Home Assistant (median state confirmation 133 ms). We evaluate three testbed workload families (Appendix § 17): (i) the four-room physical smart-home LLM application (§ 6.2); (ii) the long-running HomeSvc smart-home service (three agents, 81 tasks, early/late alerts at 0 s/15 s; § 2); and (iii) seven multi-agent workflow benchmarks of seven agents across three sites (C2 cross-team fault, C3 session-wide stale state, N2 single reader, N3 root-plan fault, and three random DAGs with 9–34 tasks; early/late alerts at 0.8 s/10.8 s), plus C2 under dynamic spread at rogue rates 0.3 and 1.0 (where tainted invocations emit undeclared in-scope effects and spawn child tasks). In the controlled grids (10.5k LoC harness), deterministic workers execute identical compiled plans and seeded faults against exact ground truth; for broad topology and spread sweeps, a discrete-event simulator executes the same controller code across 24,266 runs (Appendix § 18).

Evaluated controls and metrics. At the system layer, thin adapters run the same workload plans over Google’s A2A SDK ([1]) (cancel agent, cancel all, block input) and LangGraph ([23]) (cancel run, block and resume, time travel checkpoint rollback). At the strategy layer on EDGECITADEL, we compare AIRLOCK’s two tiers and ablations (Table 3) against topological and coarse safeguards ([38, 40, 44]) and a sink-only Exit guard (Appendix § 15). Comparison grids trigger identical ground-truth alerts (early, median 0.93 s after faulty output production, or late, after downstream readers start); dedicated grids evaluate EDGECITADEL’s built-in boundary detectors (§ 8.1) and symptom-only backward root-cause resolution (Appendix § 15). Across all controls, a run is clean after the alert if zero tainted effects commit at any protected sink from the alert until the end of the run (an identical post-alert window) without timeout; for cut policies, we additionally audit post-τ1\tau_1 leaks (effects committed at or after τ1\tau_1) to separate reaction-window leaks from post-convergence safety (Theorem 5). Completed work measures the compute-weighted fraction of healthy at-risk tasks that finish, while work kept without redo (kept work)… excludes tasks re-executed after rollback, scored from independent destination ledgers (Appendix § 16).

Strategy on EDGECITADELMain Grid (54)CostSaturated
CategoryPolicyClean ↑Kept (med.) ↑MsgsClean, Kept ↑
No containment0–00, –
Source- G-Safeguard121.02not run
- Reject source31.000, –
- Stop team150.99110, 54.0%
Coarse- Stop downstream540.383410, 25.4%
- Sink guard540.657not run
AIRLOCK- full quarantine540.831210, 54.0%
- optimized cut541.026.510, 100.0%
Ablation- Trace & stop540.947not run
- Greedy cut541.025.5not run
- Cut without deadlines541.017not run

Table 3. Strategy-layer comparison on EDGECITADEL (54 batch runs; saturated: C2 at rogue rate 1.0, 10 runs). Best (excl. No containment) bolded, worst underlined.

Physical Smart-Home Application with LLMs

Four-room smart-home application. We first evaluate AIRLOCK end-to-end on a physical smart-home application (Figure 5a) where a tree of LLM agents prepares three meeting rooms and a lobby from a shared calendar across three hosts: Host 1 runs the root planner, calendar service, and user assistant; Host 2 runs zone-a, room-r1, and room-r2; and Host 3 runs zone-b, room-r3, and a deterministic lobby agent. Room agents configure physical lamps (via EDGECITADEL’s Home Assistant gateway, monitored by lab camera and state recorder) and post room announcements (protected effects), while lobby drives lobby lamps on a fixed schedule without reading the calendar and assistant answers six user questions about the day’s schedule. We evaluate 161 scored runs across six LLM deployments: local Qwen 3.8 27B (86 runs across root and single-room calendar fault injections plus no-fault references), local Gemma 4 31B, three frontier cloud APIs (GPT 6.1 sol, Gemini 4, and

Opus 5.5), and a heterogeneous tree (root Opus 5.5 planner with downstream Qwen 3.8 27B agents). In each faulted run, a tool-boundary injection corrupts a calendar booking either at the root planner’s first read (affecting all meeting rooms) or at one room agent’s local read (room-r2).

Fault adoption and containment. Across all six model deployments, the LLM reading the corrupted calendar entry adopted the faulty booking in all faulted runs (e.g., 80 of 80 faulted Qwen runs, with at least 6 downstream agents computing on the corrupted plan under root injection). Without containment, Qwen runs committed 30 (root) and 30 (local) wrong protected effects after the alert (22/22 lamp commands, 8/8 announcements), while Gemma 4 and the cloud API models committed 75 wrong protected effects across their 20 uncontained runs (52 lamp, 23 announcements). Under both AIRLOCK tiers, 0 wrong protected effects committed after the alert across all Qwen runs at either injection point, 0 across Gemma 4 and all three frontier API models, and 0 in the mixed Opus–Qwen deployment, with 0 post-τ1\tau_1 leaks and median τ1\tau_1 of 0.164 s (root) and 0.276 s (local) on Qwen (0.168 s–0.550 s on other models).

Selective service retention and physical state audit. While both tiers achieved complete post-alert containment, they separated cleanly on service retention (Figure 5b). Under root injection, full quarantine halted the assistant completely (all 6 of 6 user questions unanswered), whereas the optimized cut revoked only protected effect classes and kept the assistant answering 5 of 6 questions correctly per run across every model (only the single question about the corrupted room was affected). Under local single-room injection, room-r2 committed only 1.8 lamp commands per run (vs. 10.0 without a fault, as its post-alert commands were held), while uninjected rooms completed all 20 scheduled lamp actuations and lobby preserved all of its automation commands. A post-hoc audit against Home Assistant’s physical state recorder across all 161 runs verified complete physical mediation: every physical lamp state transition (1,870 changes) matched a journaled gateway commit (0 unmatched; median lag 0.77 s), and 0 of the 704 gateway-held lamp commands actuated a physical lamp. On the controlled HomeSvc replica (Table 1; § 2.2), early alerts are bimodal depending on whether the schedule hold lands before the assistant’s first read (Reject source blocked the read in 5 of 5 runs, optimized cut in 1, full quarantine in 1, averaging 9.0 and 9.0 of 45 correct answers; pricing tainted replies at zero in simulation makes optimized cut block the read in all 120 paired runs), whereas across all 55 late-alert runs (5 per strategy), the schedule was already in shared memory (0 correct answers), as repairing absorbed conversational state requires orthogonal rollback.

System Layer: Agent Framework Controls

Table 2 and Figure 6a compare EDGECITADEL and AIRLOCK against the native controls of Google A2A and LangGraph on the same workload plans and faults. Because A2A tracks tasks per agent without cross-agent provenance, cancelling the faulty agent is clean in only 12 of 42 content-fault runs (28.6%) and blocking its output in 0 (0.0%): every leaked effect is emitted by a downstream peer that consumed the tainted data before the alert. Conversely, A2A’s workflow-wide cancel all stops all leaks but retains 0% of at-risk work. Both AIRLOCK tiers are clean across all content and rogue runs (42/42 and 10/10; one-sided McNemar p=9.3e−10p = 9.3\mathrm{e}{-10} and 2.3e−132.3\mathrm{e}{-13} vs. A2A per-agent controls, Fisher p=5.4e−6p = 5.4\mathrm{e}{-6} under rogue spread) while retaining a median of 83% (full quarantine) and 100% (optimized cut) of at-risk work without redo (differing by +2.9 pp over 36 pairs, p=0.46p = 0.46).

System / ControlClean Runs ↑Retained ↑
FrameworkPolicyContent (42)Rogue (10)No redo (med.)
No control00100%
A2A- cancel agent12094%
- cancel all42100%
- block input00100%
LangGraph*- cancel run18 of 186 of 60%
- block, resume6 of 183 of 6–†
- time travel18 of 186 of 616%
AIRLOCK- full quarantine421083%
- optimized cut4210100%

Table 2. System-layer comparison (42 content, 10 rogue runs; *LangGraph: 18 content, 6 rogue; †paired diff. in text). Best bolded, worst underlined.

LangGraph exhibits the complementary trade-off of state-graph frameworks: block-and-resume leaks in two-thirds of runs (clean in 6 of 18, McNemar p=2.4e−4p = 2.4\mathrm{e}{-4}), while cancel-run is clean (18 of 18) at the cost of discarding all at-risk work (median 0% kept). LangGraph’s time travel rolls the graph back to a pre-fault checkpoint and re-executes; while re-execution eventually completes a median of 100% of healthy at-risk tasks, it retains only 16% of work without redo, re-running 111 tasks, repeating 25 external actuations, and inflating late-alert makespan to 1.07× of its no-fault reference. On paired runs, the optimized cut retains +68 pp, +96 pp, and +82 pp more work without redo than block-and-resume, cancel-run (p=6.1e−5p = 6.1\mathrm{e}{-5}), and time travel.

Strategy Layer: Quarantine vs. Optimized Cut

Why provenance reachability is necessary. Fixing EDGECITADEL’s enforcement gates across 11 strategies (Table 3) isolates the impact of provenance tracing. Source-only policies leak whenever taint has crossed to peers: halting the faulty agent’s static team (Stop team (Zhou et al., [44])) is clean in 15 of 54 runs, severing its future outgoing edges (G-Safeguard (Wang et al., [38])) in 12, and blocking only its direct outputs (Reject source (Xie et al., [40])) in 3. Conversely, coarse global rules (blocking all protected effect classes in Sink guard or halting statically downstream tasks in Stop downstream) achieve 54/54 cleanliness only by halting healthy work (Stop downstream retains a median of 38% of at-risk work). A sink-only Exit guard (holding only tainted units’ protected effects) ties the optimized cut when faults do not spread (839 of 840 simulation runs), but trails by −6.2 points in kept work and −5.3 points in clean runs under active spread as unhalted units taint peers.

Two tiers and mechanism attribution. Both full quarantine and the optimized cut are clean after the alert in all 54 faulted batch runs (including all 12 rogue cells) and in all 10 runs at each of rogue rates 0.3 and 1.0 (as is the Trace & stop ablation, which holds lineage-tainted artifacts and effects without pausing invocations). Across all 279 maingrid runs that reached τ1\tau_1, our fence audit confirms that all enforced actions were journal-fenced (0 unfenced) and 0 tainted effects committed after τ1\tau_1 (median τ1\tau_1 of 0.18 s, 90th percentile 0.55 s, solve time 0.098 s). On static batch workflows and moderate spread (rogue rate 0.3), both tiers (and Greedy cut, which selects switches greedily by cost per covered edge) retain equivalent healthy work (pooled difference +4.3 pp over 48 matched runs, p=0.185p = 0.185), making full quarantine an effective low-message default (12 vs. 26.5 control messages/run). Under saturated spread (rogue rate 1.0, Figure 6b), however, full quarantine and Stop team both retain only 54.0% of at-risk work, whereas the optimized cut retains 100.0% in every run, a paired gain of +46 pp across all 10 pairs (sign-flip p=0.0019p = 0.0019); in large-scale simulation (1,860 paired runs under spread), it is also +0.91 percentage points cleaner. This retention gain comes from the selective-control tier as a whole (source-side egress labels, finer switches, and guarded admission), while laminar max-flow solves vertex-local nested switches in one max-flow call (Theorem 2) and falls back to exact enumeration or MILP under cross-vertex coupling (Proposition 3).

Detectors, Delay, Overhead, and Scale

Boundary detectors and deadline-aware selection. Without external monitors, EDGECITADEL’s authority boundary detector fired spontaneously on out-of-scope dispatches in 50 of 50 saturated rogue runs at a median latency of 136 ms (12.6 s into the run, ahead of the 19.5 s injected alert), and in a dedicated detector-triggered grid spanning authority-overreach and lease-exhaustion faults, built-in detectors caught 35 of 36 faulted runs (median latencies 179 ms and 199.5 ms; at most 649 ms), with both AIRLOCK tiers achieving clean containment and τ1≤1.0\tau_1 \le1.0 s. Under injected control delays of 1 s and 4 s (LL of 1.4 and 4.4 s on C2 and N2), all 72 cut runs still achieve fenced τ1\tau_1 convergence with 0 post-τ1\tau_1 leaks: while deadline-aware Optimized cut stays clean after the alert across all delays (0 leaks; median τ1\tau_1 scaling from 0.12 s to 1.15 s and 6.17 s), Cut without deadlines (solving the minimum cut ignoring LL and d(e)d(e)) suffers a pre-τ1\tau_1 leak at 4 s delay (clean after the alert in 11 of 12 runs, Figure 6c) by crediting slow actions that arrive after an effect commits at 12.4 s. Separately, while safety is independent of action costs c(a)c(a) (Theorem 5), pricing revocations by an agent’s expected work within its remaining resource budget raises Spearman correlation with lost compute from 0.13 (live-work heuristic) to 0.7 in an offline check (Appendix § 19).

Runtime overhead and ingestion scaling. While per-hop transactional journaling adds 165 ms–836 ms on micro-handoffs (vs. 146 ms–582 ms bare and 7 ms–50 ms on A2A-SQLite), this cost is amortized whenever agents perform real computation: across all seven workflows (Figure 6d), AIRLOCK’s end-to-end makespan is within −8.5% to +8.5% of A2A’s (+0.7% to +4.5% above bare; laminar max-flow solve: 0.022–0.031 ms; coordinator peak memory 86.4 MB). When stress-testing our single-process SQLite coordinator on a 63-agent workflow across 16, 32, and 63 logical sites on two hosts, centralized journal ingestion saturates, growing ingest lag to 52.4–90.8 s at 63 sites (Appendix § 19). In that regime, AIRLOCK’s fail-safe contract holds, marking un-ingested alerts as indeterminate, never claiming τ1\tau_1 (0 of 22), and releasing 0 holds prematurely, though effects that commit before journals arrive cannot be intercepted (1 of 22 runs clean after the alert), motivating sharded coordinator ingestion for larger clusters.

Related Work and Discussion

Agent guardrails and topological defenses. Single-agent guardrails and planner-level information-flow control restrict tool calls inside one agent ([4, 7]), complementing AIRLOCK with white-box access. Across multi-agent topologies, errors cascade rapidly ([3, 17, 40]), and prior defenses pair anomaly detection (Forough et al., 2023; Li et al., 2026) with source-local remediation: G-Safeguard severs a flagged agent’s future outgoing edges ([38]), GUARDIAN isolates the flagged agent ([44]), and From Spark to Fire filters unverified claims at the source ([40]). Severing future outgoing edges misses peers that already read the output (§ 8); AIRLOCK traces forward from such alerts on GPG_P to fence consumers.

Framework controls, revocation, and recovery. Production frameworks provide per-task cancellation ([1]) or whole-graph interrupt and checkpoint rollback ([23]), and SOUNDGATE [20] fences in-flight side effects on cancellation; EDGECITADEL adds daemon-mediated provenance for selective boundaries without workflow halts or rollback. EDGECITADEL’s delegation tree builds on capability attenuation, actuation leases, and secret isolation ([2, 42, 35, 30, 37, 8] (Forough et al. 2026)). Whereas VERA models authority loss under edge revocation ([25]) and RSQ retires an authorization root via epoch barriers ([45]), AIRLOCK contains data taint propagating within valid credentials under site deadlines. Similarly, whereas intrusion recovery traces provenance backward for offline repair ([22, 14, 21, 39]) and transactional runtimes undo single-agent actions ([29, 34]), AIRLOCK contains faults online before commit.

Limitations and future work. Appendix § 19 documents our prototype’s scope: AIRLOCK contains external effects online rather than rolling back agent memory ([39]); beyond roughly ten agents across three hosts, our single-process coordinator’s journal ingestion saturates (§ 8.1), motivating sharded ingestion, budget-aware pricing (§ 8.1), and post-incident endorsement.

Conclusion

We presented AIRLOCK, a multi-agent runtime and guardrail co-designing EDGECITADEL’s vertical permission hierarchy and lock-fenced site switches with an online provenance DAG and fence-then-prune minimum-cut containment. On our main testbed and smart-home grids, AIRLOCK blocks all post-alert faulty actuations with zero leaks after fenced convergence, retaining +68 pp to +96 pp more healthy work than A2A and LangGraph (+46 pp over full quarantine under dense spread). These results demonstrate that uniting runtime authority boundaries with online provenance breaks the all-or-nothing trade-off between safety and availability, providing a practical foundation for deploying multi-agent systems over real-world services and physical devices.

Containment as a Grouped ss–tt Cut

This appendix states the problem the controller solves and proves the results the main text uses; statement numbers match the main text. A.1 defines the live graph, the actions and the grouped cut. A.2 shows that the problem is hard in general (Proposition 1). A.3 identifies the case the runtime meets in practice, nested switches at each vertex, where one max-flow is exact (Theorem 2); Proposition 2.1 shows that the runtime’s switches fall in it, and A.4 gives the exact fallback for the rest (Proposition 3). A.5 adds deadlines (Proposition 4). A.6 proves that fence-then-prune lets no tainted effect commit after τ1\tau_1 (Theorem 5) and lists what the theorem does not cover (Table A.2). A.7 lists the machine checks behind every constructive statement.

Problem statement

Live graph. The controller works on a directed graph G=(V,E)G=(V,E) (parallel edges allowed). Vertices are live invocations uu (each holding one credential κu\kappa_u minted for it), targets bb (gateway-mediated endpoints; a sink target has an uncuttable edge b→tb\to t), a super-source ss joined by uncuttable edges to the tainted invocations, and the super-sink tt. Edges are the pending one-hop events: immediate effects (u,b,κu)(u,b,\kappa_u), scheduled effects (u,b,κu,d)(u,b,\kappa_u,d) with earliest commit time dd, messages and spawns (u,u′)(u,u'), and results (u,parent⁡(u))(u,\operatorname{parent}(u)). Each edge has an individual cost c(e)∈R≥0∪{∞}c(e)\in\mathbb{R}_{\ge0}\cup\{\infty\} (∞\infty = uncuttable). Only edges on some s→ts\to t path matter.

Actions. A finite set A\mathcal{A} of actions, each with a cost c(a)∈R≥0∪{∞}c(a)\in\mathbb{R}_{\ge0}\cup\{\infty\} and a removal set R(a)⊆ER(a)\subseteq E. Selecting C⊆AC\subseteq\mathcal{A} removes Rem⁡(C)=⋃a∈CR(a)\operatorname{Rem}(C)=\bigcup_{a\in C}R(a) (ANY semantics). Individual edge cuts are the actions with R={e}R=\{e\}. The runtime’s vocabulary is listed with its removal sets in Table A.1. No action revokes a delegation subtree; descendants are covered by their own actions and by taint-aware admission (Section A.6).

Delegation tree (special case). When actions are credential revocations with the semantics “revoking ww revokes every descendant”, the removal sets R(w)=⋃u∈sub⁡(w)E(u)R(w)=\bigcup_{u\in\operatorname{sub}(w)}E(u), with sub⁡(w)\operatorname{sub}(w) the subtree of ww, form a laminar family; we call this the tree model. It is the action model with a particular RR; nothing below depends on it except where stated.

Problem GC (grouped cut). Minimise ∑a∈Cc(a)\sum_{a\in C}c(a) over C⊆AC\subseteq\mathcal{A} such that G∖Rem⁡(C)G\setminus\operatorname{Rem}(C) has no s→ts\to t path; OPT=∞\mathrm{OPT}=\infty if no cut exists. B⊆AB\subseteq\mathcal{A} is a cut for (G,X)(G,X) if G∖Rem⁡(B)G\setminus\operatorname{Rem}(B) has no path from X⊆VX\subseteq V to tt. Removing more edges never creates a path, so cuts are closed upward. The objective is additive in actions; real work preserved is measured separately.

Scope. ANY semantics only. The ALL variant, in which an edge survives while any of several authorities is intact, is not used by the runtime; it needs set-level enforcement invariants and special handling of unwitnessed edges, and is not treated. GC is the weighted minimum label ss–tt cut problem ([19, 43]) with one label per action and multi-labelled edges; the tree model, the single-label case and the action model are cost-preservingly inter-reducible with linear blow-up (private-chain and series-split constructions; brute-force checked).

Hardness

Proposition 1 (cited: Set Cover hardness). GC is NP-hard and admits no polynomial-time (1−ε)(1-\varepsilon)-approximation for any ε>0\varepsilon>0 unless P=NPP=NP, even in the tree model with a depth-1 tree, unit action costs, every edge in exactly one removal set, no individually cuttable edge, and GG a parallel composition of s→ts\to t paths (series-parallel, planar, acyclic). It remains Set-Cover-hard when every removal set is a subset of the out-edges of a single vertex, provided the removal sets may cross.

Proof. (i) From Set Cover (U={1..n}U=\{1..n\}, sets S1,…,SmS_1,\ldots,S_m): one s→ts\to t path PiP_i per element, with one uncuttable edge per set Sj⊇iS_j\supseteq i, in R(aj)R(a_j), c(aj)=1c(a_j)=1. PiP_i is destroyed iff some selected SjS_j contains ii; s,ts,t are disconnected iff the selected sets cover UU; costs are equal, so ratios are preserved. (ii) Nodes s,v,y1..yn,ts,v,y_1..y_n,t, uncuttable s→vs\to v, v→yiv\to y_i, yi→ty_i\to t, R(aj)={v→yi:i∈Sj}R(a_j)=\{v\to y_i:i\in S_j\}: all of δ+(v)\delta^+(v) must go, which is again Set Cover.

Both reductions were checked by exhaustive enumeration (200 and 200 instances). Set-Cover hardness: Feige [10]; Dinur & Steurer [9] under P≠NPP\ne NP. GC is also W[2]W[2]-hard in the number of selected actions (Fellows et al., [11]), and APX-hard even when every removal set is the boundary of a disjoint path-shaped region of the graph (reduction from Vertex Cover; the regions then have several entry vertices).

Remark. In the instances of (i) every action is gated in the sense of Section A.3 (at (s,out)(s,\mathrm{out}) by the first edges of its paths); their gate sets cross. Gatedness alone therefore does not help (50 such instances checked); the operative condition of Theorem 2 is laminarity per port. Instance (ii) is the “star property” hardness of shared-risk group cuts ([5]) and shows the condition cannot be dropped.

The fast path: gated, per-port laminar instances

Definition (gate). A port is (v,σ)(v,\sigma), σ∈{out,in}\sigma\in\{\mathrm{out},\mathrm{in}\}, with star δσ(v)\delta^\sigma(v). Action aa is gated at (v,σ)(v,\sigma) by Πa⊆δσ(v)\Pi_a\subseteq\delta^\sigma(v) if every simple s→ts\to t path meets R(a)R(a) iff it meets Πa\Pi_a. A vertex-local action (R(a)⊆δσ(v)R(a)\subseteq\delta^\sigma(v)) is gated by Πa=R(a)\Pi_a=R(a).

Lemma A.1 (substitution). aa is gated by Πa\Pi_a iff for every

F⊆EF \subseteq E, G∖(F∪R(a))G \setminus(F \cup R(a)) is ss–tt disconnected exactly when G∖(F∪Πa)G \setminus(F \cup\Pi_a) is.

Proof. (⇒\Rightarrow) a simple path survives F∪R(a)F \cup R(a) iff it avoids FF and R(a)R(a) iff it avoids FF and Πa\Pi_a. (⇐\Leftarrow) if a simple path PP meets R(a)R(a) but not Πa\Pi_a, take F=E∖PF = E \setminus P.

Chain gadget GγG^\gamma. Let A′A' be the finite-cost actions, each assigned to one port π(a)\pi(a) at which it is gated by Πa\Pi_a, such that at every port the family Lp={Πa:π(a)=p}\mathcal{L}_p = \{\Pi_a : \pi(a) = p\} is laminar (equal sets merged, keeping the minimum cost). For each port (v,out)(v,\mathrm{out}): one node aSa_S per set S∈LpS \in\mathcal{L}_p, and an edge anchor⁡(S)→aS\operatorname{anchor}(S) \to a_S of capacity c(S)c(S), where anchor⁡(S)\operatorname{anchor}(S) is the node of the smallest S′⊋SS' \supsetneq S in Lp\mathcal{L}_p, or vv if none (mirrored at in-ports: aS→anchor⁡(S)a_S \to\operatorname{anchor}(S)). For each edge e=(x,y)e = (x,y), let SeS_e be the smallest set of L(x,out)\mathcal{L}_{(x,\mathrm{out})} containing ee and TeT_e the smallest set of L(y,in)\mathcal{L}_{(y,\mathrm{in})} containing ee (either may not exist); add one edge src⁡(e)→dst⁡(e)\operatorname{src}(e) \to\operatorname{dst}(e) of capacity c(e)c(e), with src⁡(e)=aSe\operatorname{src}(e) = a_{S_e} or xx, dst⁡(e)=aTe\operatorname{dst}(e) = a_{T_e} or yy. GγG^\gamma has ∣V∣+∣A′∣|V| + |A'| nodes and ∣E∣+∣A′∣|E| + |A'| edges.

Theorem 2 (fast path). If every finite-cost action is gated at its assigned port and the gate families are laminar at every port, then OPT equals the minimum ss–tt cut of GγG^\gamma, and an optimal action set is read off the cut (an action is selected iff its chain edge is cut; an edge is cut iff its gadget edge is). One max-flow on ∣V∣+∣A′∣|V| + |A'| nodes.

Proof sketch. By Lemma A.1 applied action by action (it holds for every FF), CC is a cut iff ⋃a∈CΠa∪CE\bigcup_{a\in C}\Pi_a \cup C_E is an edge cut, so each action may be replaced by its gate set. A simple s→ts \to t path PP of GG maps to the path γ(P)\gamma(P) of GγG^\gamma that, at each edge e=(x,y)e = (x,y), descends the out-chain at xx to aSea_{S_e} (if SeS_e exists), crosses the gadget edge of ee, and ascends the in-chain at yy from aTea_{T_e} (if TeT_e exists). Conversely a gadget node at (x,out)(x,\mathrm{out}) is entered only from xx or its parent and left only towards a child or along a gadget edge of an edge in its set, and symmetrically at in-ports, so every simple s→ts \to t path of GγG^\gamma is γ(P)\gamma(P) for a unique PP: no spurious connectivity. Cutting the chain edge of Πa\Pi_a separates exactly the paths γ(P)\gamma(P) with P∩Πa≠∅P \cap\Pi_a \ne\varnothing (by laminarity, the chain from xx to aSea_{S_e} passes through every set at the port that contains ee), and cutting the gadget edge of ee separates exactly the γ(P)\gamma(P) with e∈Pe \in P. Hence cuts of GγG^\gamma of finite capacity and cuts of the substituted instance correspond with equal cost.

Brute-force checks: 300 gated instances, 300 laminar-forest instances, and 200 flat instances with families at both edge ends.

Proposition 2.1 (runtime mapping). Under single credentials (each credential held by one invocation, each effect edge under one credential) and the port assignment of Table A.1, every action is vertex-local and the families are laminar at every port: at (u,out)(u,\mathrm{out}), R(task hold)⊇R(egress hold)⊇R(revoke κu)R(\text{task hold}) \supseteq R(\text{egress hold}) \supseteq R(\text{revoke }\kappa_u) and singletons; at (b,in)(b,\mathrm{in}),

ActionSiteR(a)R(a)Port
task hold on uuhost⁡(u)\operatorname{host}(u)all pending egress edges of uu(u,out)(u,\mathrm{out})
egress hold on uugatewayimmediate effect edges out of uu(u,out)(u,\mathrm{out})
revoke κu\kappa_uverifiereffect edges out of uu under κu\kappa_u(u,out)(u,\mathrm{out})
filter (κu,b)(\kappa_u,b)ingress(b)(b)effect and scheduled edges (u,b)(u,b) under κu\kappa_u(b,in)(b,\mathrm{in})
admission block at bbingress(b)(b)all effect and scheduled edges into bb(b,in)(b,\mathrm{in})
scheduled-effect, result or admission hold on eescheduler, host or admitting site{e}\{e\}either

Table A.1. The runtime vocabulary and its removal sets.

R(block b)⊇R(filter(κ,b))R(\text{block }b) \supseteq R(\text{filter}(\kappa,b)) with filters for different credentials disjoint, and singletons. Hence Theorem 2 applies.

Configurations that violate the hypotheses, and are detected by the check: a credential shared by several invocations (the revocation is not vertex-local); an effect that requires several credentials (crossing revocation sets); deadline masks under non-monotone latencies (Proposition 4(c)); a two-port action (filter, singleton hold) placed at the wrong port. Of 300 runtime-vocabulary instances, all 150 with monotone latencies and 148 of 150 with random latencies passed the check; the other 2 were correctly routed to the exact fallback.

The check. On every instance (each graph, source or deadline update) the solver computes the removal sets (masks), verifies vertex-locality syntactically, assigns each action to a port (actions with two candidate ports, parallel u→bu \to b edges only, are assigned by 2-SAT over crossing pairs), and verifies laminarity per port, at cost O(∣A′∣2max⁡a∣R(a)∣)O(|A'|^2 \max_a |R(a)|). If the check passes, one max-flow; otherwise Proposition 3. Exactness is claimed only for instances that pass.

Fallback

Proposition 3 (exact fallbacks). (a) Exception set. Let Y⊆A′Y \subseteq A' be a declared set such that A′∖YA' \setminus Y satisfies the hypotheses of Theorem 2 on GG. Then OPT is computed by at most 2∣Y∣2^{|Y|} max-flows: for each C⊆YC \subseteq Y, delete Rem⁡(CY)\operatorname{Rem}(C_Y), solve the residual instance by Theorem 2, and d(CY)d(C_Y), and take the minimum. (b) ILP. With binaries yay_a and potentials πv∈[0,1]\pi_v \in[0,1],

min⁡∑ac(a)yas.t.πs=1, πt=0,\min\sum_a c(a)y_a \quad\text{s.t.}\quad\pi_s = 1,\ \pi_t = 0,
πtail⁡(e)−πhead⁡(e)≤∑a:e∈R(a)ya(∀e∈E),\pi_{\operatorname{tail}(e)}-\pi_{\operatorname{head}(e)} \le\sum_{a:e\in R(a)} y_a \qquad(\forall e\in E),

is exact, with ∣E∣+2|E|+2 constraints and ∑e∣{a:e∈R(a)}∣\sum_e |\{a:e\in R(a)\}| nonzeros. (c) Approximation. Giving each edge the cost of

A.4

ends_mid=1 its cheapest covering action and taking an ordinary min cut is an ff-approximation, f=max⁡a∣R(a)∣f = \max_a |R(a)|.

Proof. (a) The branch CY=C∩YC_Y = C \cap Y of an optimal CC is enumerated; in it the best completion is the residual optimum. Gates survive edge deletion (the gate condition is per simple path and the residual has fewer), and laminarity survives intersecting every set with a fixed edge set. (b) For integral yy the potential system is feasible iff Rem⁡({a:ya=1})\operatorname{Rem}(\{a : y_a = 1\}) is a cut (set πv=1\pi_v = 1 iff vv is reachable from ss in the surviving graph); an uncuttable edge covered by no action yields πtail≤πhead\pi_{\mathrm{tail}} \le\pi_{\mathrm{head}}. (c) The optimal grouped solution induces an edge cut of modified cost at most f⋅OPTf \cdot\mathrm{OPT}. □ The enumeration (a) was checked by brute force on 200 random instances with 1–3 exceptions.

Remark (why YY is an exception set and not “the ungated actions”). Three parallel paths s→a→ts \to a \to t, s→b→ts \to b \to t, s→c→ts \to c \to t with actions A={s→a,s→b}A = \{s \to a, s \to b\}, B={b→t,s→c}B = \{b \to t, s \to c\}, C={a→t,c→t}C = \{a \to t, c \to t\}, unit costs, all edges uncuttable: every action is gated (at (s,out)(s,\mathrm{out}) and at (t,in)(t,\mathrm{in})), yet the gate sets pairwise cross and no port assignment is laminar (0 laminar assignments exist); OPT=2\mathrm{OPT} = 2. Theorem 2 does not apply with Y=∅Y = \varnothing; it does with Y={A}Y = \{A\}. The runtime declares YY by vocabulary (the configurations listed under Proposition 2.1); it never searches for a minimum one, and the ILP is exact regardless.

Deadlines

Model. Decision time tnowt_{\mathrm{now}}, planning allowance β\beta, enactment latency upper bound L(σ(a))L(\sigma(a)) of the site at which aa is enacted, and for each edge ee a conservative lower bound d(e)d(e) on its earliest commit time (∞\infty for an edge currently removed by a confirmed in-force action; exact under gateway not-before scheduling; tnowt_{\mathrm{now}} for an unheld immediate effect). The timely mask of aa is R^(a)={e∈R(a):tnow+β+L(σ(a))<d(e)}\widehat{R}(a) = \{e \in R(a) : t_{\mathrm{now}} + \beta+ L(\sigma(a)) < d(e)\}, and an action in force takes its mask from confirmed state. For a mask to certify timely enactment, each credited command must be issued within β\beta of tnowt_{\mathrm{now}}, and LL then bounds its remaining enactment time, including queueing at the site; the runtime uses β\beta as a configured prediction, not a solver timeout, and neither measures nor enforces the first bound. Exceeding either bound invalidates the timing prediction, and convergence still requires the fenced-state check below. There is no tree semantics for timely removal: in the tree model each witness has its own mask and no antichain convention.

Proposition 4 (deadlines). (a) Iβ=(G,A,c,R^)I_\beta= (G, A, c, \widehat{R}) is an instance of the action model; CC is a feasible cut iff Rem⁡^(C)\widehat{\operatorname{Rem}}(C) is an edge cut; every hardness result holds for IβI_\beta; Theorem 2 applies to IβI_\beta iff the masks pass the check, and Proposition 3 applies always. (b) Ancestor redundancy fails. Vertex vv with out-edges e1,e2,e3e_1, e_2, e_3 to tt of individual cost 100; parent pp, c(p)=1c(p) = 1, R(p)={e1,e2,e3}R(p) = \{e_1, e_2, e_3\}, R^(p)={e1,e3}\widehat{R}(p) = \{e_1, e_3\}; child uu, c(u)=10c(u) = 10, R(u)={e1,e2}R(u) = \{e_1, e_2\}. OPT(Iβ)=11\mathrm{OPT}(I_\beta) = 11 by selecting both pp and uu; the antichain convention yields 101, and the untruncated tree semantics (ru≥rpr_u \ge r_p) yields 1 while falsely reporting e2e_2 removed. (c) If R(a)⊆R(b)R(a) \subseteq R(b) and L(σ(b))≤L(σ(a))L(\sigma(b)) \le L(\sigma(a)) then R^(a)⊆R^(b)\widehat{R}(a) \subseteq\widehat{R}(b), and disjoint sets stay disjoint; hence laminarity at a port survives truncation when latency is non-increasing along inclusion (always when the nested actions share a site, as filters and blocks do). (d) Vertex-locality survives truncation; a single-edge gate survives if the gate edge stays in the mask (sufficient, not necessary); a sealed region may leak. (e) R^β′(a)⊆R^β(a)\widehat{R}_{\beta'}(a) \subseteq\widehat{R}_{\beta}(a) for β≤β′\beta\le\beta', so a larger budget never lowers OPT\mathrm{OPT} and may make the instance infeasible.

Proof. (a), (c), (d) and (e) are immediate from the definition; (b) is exhaustive enumeration, also against the literal ILP of Proposition 3(b). □

The masks are predictions; the fenced confirmations of Section A.6 are ground truth. An action whose mask is a proper subset of its removal set is paid in full and must be modelled per site. During refinement, an edge already held by a confirmed in-force action has d=∞d = \infty, and every other edge keeps its literal deadline mask. The distinction matters for adaptive phase 1, whose source side may contain uncovered edges: a replacement action is credited only where it can take effect before the edge commits, and guarded release checks the resulting cut. Under the full-frontier freeze every pending source-side edge is held, so the literal masks are safe but conservative there, and truncation genuinely constrains only a solve that no in-force cut protects (a one-shot deadline-aware cut, or a partial phase 1).

Safety of the two-phase protocol

Model. Every site keeps an ordered journal of commits, admissions and confirmations; the controller ingests journals, and “time” below is its reconciled state. The live graph G(τ)G(\tau) holds the pending one-hop edges; a commit of e=(x,y)e = (x,y) removes ee from GG and, if xx is tainted, taints yy; a commit into tt with a tainted tail is a leak (tt itself is never tainted). X(τ)X(\tau) is the taint set, grown only by journaled commits from the declared source set X(τ0)X(\tau_0). A(τ)A(\tau) is the set of actions confirmed at every site that enforces them (a partially released action is not in AA). The assumptions are:

  • (F) Fenced confirmation and commit-time re-check. A site confirms action aa with a journal position jj such that every commit of an edge of R(a)R(a) at that site precedes jj, and no edge of R(a)R(a) commits there after jj while aa is in force (the gateway re-validates holds and revocations at the commit point of every effect); the controller counts aa as confirmed at the site only after ingesting its journal through jj. Mediation completeness: every edge of GG commits through a site that enforces the actions covering цыя

it.

  • (AI) Admission invariant. The controller pushes a quarantine label set Q(τ)Q(\tau) to the sites. A new edge whose tail is labelled is held at admission by an admission hold that is in force before the edge can commit (the site journals the admission and the hold as one event). The controller keeps Q(τ)⊇S(τ):=Reach⁡G(τ)∖Rem⁡(A(τ))(X(τ))Q(\tau) \supseteq S(\tau) := \operatorname{Reach}_{G(\tau)\setminus\operatorname{Rem}(A(\tau))}(X(\tau)), the source side of the cut in force, and confirms a label push before any release that can enlarge SS.

  • (R) Guarded release. An action aa (including an admission hold) is released only if A(τ)∖{a}A(\tau) \setminus\{a\} is a cut for (G(τ),X(τ))(G(\tau), X(\tau)) on the reconciled state.

  • (J) Consistent reconciliation. Journals are per site; a commit’s taint effect depends on its tail’s taint at commit time, possibly decided by a commit on a slower site, and the fence positions of (F) cover only commits of covered edges. A solve or release check therefore uses either a consistent snapshot (every labelled site’s journal ingested through a common watermark, commits processed in timestamp order) or the conservative rule (J′): “a known commit taints its head if its tail is on the controller’s source side when the commit is reconciled”.

Messages. A message or spawn edge (u,u′)(u,u') is admitted at the sender’s site, where (AI) applies to uu, and commits at the receiver’s admission point (the claim of the new task, or delivery to a live u′u'). In between it is a pending edge of G(τ)G(\tau), also after uu finishes, so G(τ)G(\tau) contains every in-flight message (the case of Zhu & Wang [45], §2.4); by mediation completeness an action covering it is enforced at the receiver. Its content, and so its taint, is fixed at the send; taking the tail’s taint at the commit, as the model does, over-approximates it.

Trust and faults. Sites, their journals, the gateway and the controller are trusted and non-Byzantine: they fail only by crashing or partition, and a journal records what its site did. Faults are non-adversarial: an agent may act on corrupted data or malfunction, but does not target the enforcement mechanism; adversarial agents are out of scope. This is why journals and confirmations are taken as reported, not authenticated (contrast the authenticated evidence of Zhu & Wang [45]).

Effect linearization and end-to-end scoring. At the gateway, effect admission and action enforcement acquire the same per-site control lock, linearizing every effect commit against fence positions ((F)). While Theorem 5 bounds effects linearized from τ1\tau_1 onward (classifying effects accepted before τ1\tau_1 as pre-convergence, S3), our empirical evaluation applies a strictly stronger end-to-end criterion: outcomes are scored directly from external destination ledgers and physical device state (Appendix § 16), counting a run as clean after the alert only if zero tainted effects reach a protected sink at any time after the alert timestamp, including during the pre-τ1\tau_1 convergence window.

Phase 1. Let UU be the set of vertices reachable from XX by edges that no action can remove (untruncated removal sets; see Table A.1 typically U=XU = X), and B1B_1 a set of actions whose removal sets cover δ+(U)\delta^+(U) (task holds on every invocation in UU, scheduled-effect holds on frontier scheduled effects, admission blocks at targets in UU), applied at once with the labels Q:=UQ := U. If t∉Ut \notin U then, once B1B_1 is confirmed, every edge of δ+(U)\delta^+(U) is held, so B1B_1 is a cut for (G,U)⊇(G,X)(G,U) \supseteq(G,X); if t∈Ut \in U no cut exists (every edge leaving UU is coverable, else its head would be in UU). Phase 1 converges at the instant τ1\tau_1 when the convergence check K1–K4 of Theorem 5 holds; otherwise UU and B1B_1 are recomputed. Confirming all of B1B_1 everywhere is a sufficient, stricter form. Deadline masks play no role in phase 1: every covering action is applied, and the journal decides which edges crossed.

Phase 2. Solve (G(τ1),X(τ1))(G(\tau_1),X(\tau_1)) with the masks of the previous subsection (in-force actions with confirmed masks) by Theorem 2 or Proposition 3, obtaining B2B_2; apply B2∖B1B_2 \setminus B_1; wait for fenced confirmations; re-check that A∖(B1∖B2)A \setminus(B_1 \setminus B_2) is a cut on the reconciled state; release B1∖B2B_1 \setminus B_2 under (R).

Theorem 5 (two-phase safety, dynamic 1-hop runtime). Assume (F), (AI), (R), (J), mediation completeness, and that X(τ0)X(\tau_0) contains the true sources. Let τ1\tau_1 be the first instant at which the convergence check holds literally: (K1) every action the check relies on is confirmed with its fence position at every enforcing site, and every site’s journal is ingested through those positions; (K2) labels are confirmed on the whole source side S(A(τ1))S(A(\tau_1)), including tainted contexts with no live invocation; (K3) X(τ1)X(\tau_1) is reconciled from the journaled commits under (J); (K4) A(τ1)A(\tau_1) is a cut for (G(τ1),X(τ1))(G(\tau_1),X(\tau_1)) against every protected sink. (Under the full-frontier B1B_1, once all of it is confirmed, S=US = U, so K2 is the labels Q:=UQ := U.) Then for every τ≥τ1\tau\ge\tau_1, A(τ)A(\tau) is a cut for (G(τ),X(τ))(G(\tau),X(\tau)). Consequently no tainted-tail effect commits at a protected sink after τ1\tau_1: during phase 2, during the site-by-site release of B1∖B2B_1 \setminus B_2, and afterwards, whatever new events the agents produce.

Proof sketch. Invariant: t∉S(τ)t \notin S(\tau) and Q(τ)⊇S(τ)Q(\tau) \supseteq S(\tau); it holds at τ1\tau_1. Induction over the ingested events. Commit of e=(x,y)e = (x,y): by (F) and mediation completeness e∉Rem⁡(A)e \notin\operatorname{Rem}(A); if x∈X⊆Sx \in X \subseteq S then y∈Sy \in S already, so SS is unchanged and y≠ty \ne t; if x∉Xx \notin X nothing is tainted and ee leaves GG. Admission of e=(x,y)e = (x,y): if x∈Qx \in Q the edge enters held (AI); if x∉Q⊇Sx \notin Q \supseteq S it is unreachable from XX; SS is unchanged. Confirmation of an action or label push: AA or QQ grows; SS shrinks or stays. Guarded release of aa: by (R) the new source side avoids tt and its labels were pushed first; while aa is released site by site, A⊇A∖{a}A \supseteq A \setminus\{a\}, so the invariant holds throughout. Withdrawal of a label from xx: a label is withdrawn only for a vertex outside the source side after the release, which (R) with taint-aware admission guarantees (the labels for that side are pushed and confirmed before the release); SS stays inside that side during the release (A⊇A∖(B1∖B2)A \supseteq A \setminus(B_1 \setminus B_2)), so x∉Sx \notin S throughout and Q⊇SQ \supseteq S is kept. A profile that disables taint-aware admission while keeping the phase-1 freeze can withdraw labels on the post-release source side; it is outside the theorem’s hypotheses. Removal of executed edges or finished invocations: SS shrinks. □

Protocol remarks and scope. The convergence check evaluates K1–K4 on a candidate action set to three outcomes: CONTAINED when K1–K4 hold, NOT_CONTAINED when t∈Ut \in U (OPT =∞= \infty) or a path from XX to a protected sink survives in G∖Rem⁡(B)G \setminus\operatorname{Rem}(B), and INDETERMINATE when any required fence position, label confirmation, or journal watermark is missing (e.g., at a partitioned or lagging site). Only CONTAINED licenses a phase-2 release under (R); NOT_CONTAINED retains all holds and adds actions, while INDETERMINATE retains all holds and waits. Under the consistent-snapshot rule of (J), the reconciled taint set XJ(C)X_J(C) is the least fixpoint over timestamp-ordered commits through the watermark and is independent of inter-site ingestion order; under the conservative rule (J′), X(τ)⊇XJ(C)X(\tau) \supseteq X_J(C) over-approximates taint so Theorem 5 holds under every ingestion order. Once the phase-2 release of B1∖B2B_1 \setminus B_2 completes at τr\tau_r, only edges in Rem⁡(B2)\operatorname{Rem}(B_2), irreversible actions from phase 1, or admission holds remain in force, and any admission hold whose tail lies outside S(τ)S(\tau) can be released immediately under (R). Finally, if phase 1 issues only the at-alert deadline-aware cut BaB_a (adding the frontier freeze only when BaB_a is infeasible or within a slack margin), Theorem 5 still holds after τ1\tau_1 provided K1–K4 are checked on the full source side S(Ba)S(B_a) under (J) and literal masks (verified across 400 discrete-model runs per variant: 0 post-τ1\tau_1 leaks under the full conditions vs. 31 leaks when labelling UU only and 26 benign re-check refusals without literal masks). Table A.2 summarizes the scope boundaries of Theorem 5 (S1–S10).

Verification summary

All constructive reductions and gadget claims were verified by exhaustive enumeration on random instances: Set-Cover and Vertex-Cover reductions (200 and 200), the chain gadget (300 forest instances, 200 flat instances with two-sided edges, and the runtime-vocabulary instances in Section A.3), exception-set enumeration (200), the deadline and crossing-gate counterexamples, and the two-phase protocol in a discrete runtime model (400 runs per variant plus two deterministic scenarios; 21 checks pass, 0 fail).

S1Liveness. A partitioned or lagging site can prevent τ1\tau_1 from arriving; fail-closed site leases keep the set safe by holding new and pending effects upon expiry, at the cost of liveness.
S2Executed effects. Committed external effects are not rolled back; Theorem 5 governs commits after τ1\tau_1.
S3Pre-containment effects. Effects that commit between the alert and τ1\tau_1 (or are accepted under the gateway lock before τ1\tau_1) are counted as pre-τ1\tau_1 commits, separate from post-τ1\tau_1 safety.
S4Declared sources. Safety is relative to the declared initial source set X0X_0.
S5Cost optimality. B2B_2 is cost-optimal for the τ1\tau_1 snapshot and mask model; any valid cut is equally safe under Theorem 5.
S6Mediation. External effects must pass through a site or gateway that enforces A.4.
S7Masks vs. fences. Deadline masks R^(a)\hat{R}(a) are planning predictions; convergence and release rely on fenced journal positions.
S8Irreversible actions. Irreversible phase-1 actions (e.g., credential revocation) cannot be lifted in phase 2 and are priced accordingly.
S9Healthy work. Theorem 5 is a safety guarantee; healthy work retention is evaluated empirically (Section 5).
S10Persistent shared-memory services. In task-scoped workflows, invocation labels Q(τ)Q(\tau) satisfy K2 and (AI) directly. For persistent multi-turn agents sharing state across external user requests (HomeSvc), full quarantine pauses the agent to block all subsequent turns and transitive dispatches, whereas optimized cut revokes the agent’s protected sink classes before τ1\tau_1 so that no protected actuation can commit while read-only user replies remain available (if a shared-memory agent can also dispatch to downstream agents that hold protected sink authority, K2 requires either pausing the shared context or propagating taint on its outbound dispatches).

Table A.2. Scope boundaries of Theorem 5.

Runtime Artifact, Baselines, and Per-Cell Results

Open-source runtime and controls. The open-source EdgeCitadel distributed agent runtime [42] underlying Airlock is publicly available at https://github.com/EdgeCitadelTeam/EdgeCitadel. Table B.1 lists the evaluated controls. The paper names Airlock’s two settings by what they do; the registrations in Appendix § 16 use the names under which the experiments ran.

Per-cell results. With 3 repetitions per cell, we summarize the main grid’s cells by one rule instead of tabulating them: a setting wins a cell if its mean kept work is at least 5 points higher, and the win is clear if the 95% bootstrap intervals do not overlap. Of the 16 cells with at-risk healthy work, the optimized cut won 5 against full quarantine (1 clear), tied 9 and lost 2 (0 clear); pooled over 48 matched runs the difference is +4.3 pp (95% interval −1.8 to +10.6 points, p=0.185p = 0.185). The clear win is rand-n7-s1 at the late alert (+51.5 points); the two losses are C3 at the early alert (−14.8) and rand-n7-s0 at the late alert (−30.9). By the same rule the optimized cut won 3 cells against Cut without deadlines (2 clear), tied 11 and lost 2, and against Greedy cut won 2, tied 11 and lost 3. On these seven-agent DAGs, individual tainted branches typically expose only one or two candidate cut points, so greedy selection often coincides with the exact minimum cut at native latency. However, because the laminar max-flow fast path (Theorem 2) solves the exact cut in 0.022–0.031 ms (§ 8.1)—orders of magnitude below network and journaling latency—AIRLOCK achieves exact polynomial-time optimality at negligible cost, avoiding both the Θ(ln⁡n)\Theta(\ln n) worst-case approximation gap of greedy selection on shared removal sets (Proposition 1) and the pre-τ1\tau_1 safety leak of Cut without deadlines under 4 s control delay (Proposition 4, § 8.1), while retaining +46 pp more healthy work than full quarantine under dense rogue spread (§ 8) and +51.5 points more on rand-n7-s1.

ControlOriginEnforcement scope
G-Safeguardtopological [38]flagged agent: egress revoked, results parked
Reject sourcesource filter [40]faulty source’s outputs blocked
Stop teamteam halt [44]faulty agent’s entire team stopped
Stop downstreamgraph haltall tasks downstream of source stopped
Sink guardclass gateall protected effect classes blocked globally
Exit guardsink-only ruletainted units’ protected effects held
Trace & stopAIRLOCK ablationlineage-touched artifacts/effects held only
Full quarantineAIRLOCK (default)Trace & stop + pause and egress-revoke tainted units
Optimized cutAIRLOCK (assured)deadline-aware min-cost cut, two-phase protocol
Greedy cut; Cut without deadlinesAIRLOCK ablationsgreedy cut; exact cut ignoring deadlines
A2AA2A Project, 2026cancel agent, cancel all, block input
LangGraphLangChain, 2026cancel run, block and resume, time travel

Table B.1. Evaluated controls across the strategy layer (sharing EDGE­CITADEL, alert timing, and enforcement gates) and system layer (comparing end-to-end agent frameworks).

Symptom-only root-cause narrowing

When an alert reports only a downstream symptom rather than the originating invocation, the controller traverses GPG_P backward from the symptom to rank candidate upstream root causes before tracing forward. In simulation (under stress latency with a late alert on the first contaminated downstream artifact), backward ranking placed the true faulty invocation first in 37% of instances and within the top three in 97%. In a 36-run testbed grid (36 runs across C2, N2, N3, and one random workflow ×\times optimized cut, Greedy cut, and Trace & stop), each control received a single symptom-only alert and initiated containment from the single top-ranked candidate. With one symptom alert and no healthy contrast outputs, all upstream ancestors on the symptom path share the same evidence score and are ordered by graph distance: the symptom invocation itself ranks first (distance 0) and the true upstream origin ranks second in all 36 of 36 runs (tied on score with earlier ancestors). Starting containment from the distance-0 symptom alone suffices when all downstream effects lie within the symptom’s closure (9 of 12 runs clean for optimized cut, 9 for Greedy cut, 9 for Trace & stop), but misses sibling branches fed by the upstream origin in N3 (0 of 9 clean). Thus, a single symptom alert narrows candidate origins to the upstream ancestor chain on GPG_P, whereas isolating a single upstream ancestor without ties requires either healthy contrast outputs or seeding X0X_0 with the candidate ancestor set.

Pre-registration, scoring, and amendments

We recorded each experimental hypothesis and its decision thresholds in the project’s internal decision log on the date shown in Table C.1, prior to running the corresponding evaluation grid (no external registry was used). In the registration records, the system’s internal name (“cut mode” in H15) denotes optimized cut, “Trace & quarantine” (“quarantine mode”) denotes full quarantine, and “RT-full” / “RT-bare” denote EDGECITADEL with and without the provenance and containment layer.

Scoring and statistical protocol. All safety and work-retention metrics are scored from independent destination ledgers at each sink rather than from runtime journals. A run is scored as clean after the alert iff zero tainted protected effects reach a sink after the alert timestamp, and as achieving fenced τ1\tau_1 iff every action in force for the incident across all controller decisions is confirmed with its site journal fence position (verified across all 279 converged runs in the main, HomeSvc, system-comparison, and control-delay grids, with 0 unfenced runs outside the saturated 63-agent ingest stress test). Completed work measures the compute-weighted fraction of healthy at-risk tasks that finish; work kept without redo (kept work) excludes tasks re-executed after checkpoint rollback (so LangGraph time-travel re-executions count as redone), and refused hand-offs into the declared tainted closure do not penalize the healthy upstream sender. In the system comparisons (H10, H10-LG, H15), paired clean-rate comparisons use one-sided exact McNemar tests (content faults) and one-sided Fisher exact tests (rogue faults) at α=0.05\alpha= 0.05, while paired kept-work comparisons (H10, H10-LG, H14, H15) use one-sided sign-flip permutation tests at α=0.05\alpha= 0.05.

IDPredictionRegisteredOutcomeMain text
H1With rogue spread, the optimized cut contains more runs than Trace & stopby Oct 22Not supported: both clean in every rogue run of the main grid (12 and 12 of 12)Table 3
H2Without rogue spread, Trace & stop keeps at least as much workby Oct 22Not supported: Trace & stop keeps lessTable 3
H3As control latency grows, Cut without deadlines leaks more than the optimized cutby Oct 22Holds weakly: one run leaked at 4 s (11 of 12 clean), none of the optimized cut’s§5.5
H4The optimized cut issues fewer control operations than Greedy cutby Oct 22Not supported: 16 vs. 17 logical actions, 26.5 vs. 25.5 messages (medians)Table 3
H5GCG_C stays flat with live workload while GPG_P growsby Oct 22Holds (sim.): over 40 workflow instances GPG_P grows from 310 to 8,164 nodes, while GCG_C has 371 and then 311—
H6Sink guard contains about as much but keeps less workOct 21Holds (sim.)—
H7Full quarantine contains less at higher latencyOct 21Refuted on the random sweep; holds only on C2 (sim.)—
H8HomeSvc: no tainted lamp command and ≥90%\ge90\% of requests answered; full quarantine and Stop team answer noneOct 21Fails on one clause: full quarantine answered all 45 requests in the one early-alert run that blocked the read; the other clauses hold§ 2.2, § 6.2
H9HomeSvc: report the optimized cut’s tainted replies and added latencyOct 21Reported: 35.6 and 32.6 tainted replies per run (full quarantine 0); added latency 0.19 s and 0.88 sTable 1
H10Containment against A2A’s native controlsOct 21Holds in all four parts§ 7
H10-LGContainment against LangGraph’s native controlsOct 21(a) and (b) hold; (c) in part: time travel’s late-alert makespan is 1.07×1.07\times its reference, below the registered 1.2×1.2\times§ 7
H11Overhead without faults within fixed boundsOct 21Fails as registered: per-hop hand-offs exceed the bounds (e.g., 12.2×12.2\times A2A-SQLite’s, bound 3×3\times); makespan stays within its ±10%\pm10\% bound§ 8.1
H12Scaled testbed: no tainted commit after τ1\tau_1 at any site countOct 24Fails: no run reached τ1\tau_1 (0 of 22); 1 of 22 clean after the alert§ 8.1
H12-simThe simulator agrees with the scaled testbed at 32 sitesOct 24Not borne out (Appendix § 18)—
H13Built-in detectors trigger containmentOct 23H13a fails as written: 35 of 36 runs detected, the miss a hand-off failure; the other clauses hold§ 8.1
H14Containment under added control delayOct 24H14a holds; H14b holds except the predicted rise in freezes; H14c null§ 8.1
H15Full quarantine against the optimized cut under rogue spreadOct 24H15a: a tie, both clean in every run; H15b: the cut keeps more work at rogue rate 1.0§ 8
H16Meeting-room applicationOct 24H16a and H16b hold; H16g not decided as registered, checked post hoc against Home Assistant’s history§ 6.2

Table C.1. Registered hypotheses and their outcomes, using the paper’s terminology (the system’s internal name in registration logs denotes optimized cut; “Trace & quarantine” denotes full quarantine). Dates are in 2026; each registration preceded its grid’s first run. “Sim.” marks outcomes evaluated in simulation.

Protocol amendments. Five pre-scoring protocol refinements were recorded during testbed bring-up: (i) after initial pilot tail latencies exceeded the 150 ms planning estimate,

the site control-latency bound was fixed to L=400L = 400 ms across all native testbed grids (and L=L = added delay + 400 ms in the H14 delay sweep); (ii) the LangGraph comparison (H10-LG) was executed on a 129-run representative subset (C2, C3, and rand-n7-s1, three repetitions per cell) with unchanged statistical thresholds; (iii) in saturated rogue cells (ρ=1.0\rho= 1.0), where EDGECITADEL’s built-in authority boundary detector fires before the harness’s scheduled alert, runs are scored from the earliest alert on the fault lineage and reported separately; (iv) in HomeSvc (H8), service availability is scored on correct (uncontaminated) replies rather than raw reply count; and (v) the 63-agent scaling sweep (H12) was evaluated at 16, 32, and 63 logical sites after default daemon listen-backlog saturation at 3 and 8 sites, and re-verified on the released controller build (H12-A2): the registered replay check flags 12 post-run releases (0 during the run), while a post-hoc check confirms that all 1,690 of 1,690 actions in those releases were covered by the converged record’s fence positions before release (0 uncovered).

Authority and influence in the C2 workload

Figure D.1. Authority and influence in the C2 workload: gray tree edges show delegation, red arrows data influence across branches. Leaf A1 produces a wrong artifact W, which reaches the final report and, through B2’s tainted task (red), the team-B device that B2 also commands from healthy tasks (gray). Blue bars: one valid cut at the late alert.

Workloads and Detection Delays

WorkloadAgentsTasksFaultAlert (early / late)
Meeting roomsLLM delegation tree; one corrupted booking injected at calendar read (root or local room)
HomeSvc (svc)381wrong device schedule; shared memory0 s / 15 s
C2717wrong value crosses teams0.8 s / 10.8 s
C3716stale version, session-wide0.8 s / 0.8 s
N279single downstream reader0.8 s / 0.8 s
N3714corrupted root plan0.8 s / 0.8 s
rand (3)727–343 random DAG workflows0.8 s / 0.8 s

Table D.1. Evaluated workloads. Counts are workload design constants; alerts fire at fixed wall-clock delays after the faulty output is produced (early) or after its last consumer starts (late).

Workloads. A workflow benchmark is a plan of seven agents on three sites that a deterministic worker executes step by step through the runtime; faults and rogue draws are seeded by task identifiers, so the same plan produces the same messages and effects under every control (Table D.1). C2 (Fig. D.1): a leaf in one team produces a wrong artifact that its teammate passes to both leaves of the other team, where one commands a device; the root’s final report is also protected, and the other team has healthy device work. It tests cross-team spread into a physical action. At rogue rates 0.3 and 1.0 tainted invocations also take undeclared actions and spawn tasks (at most 200); at rate 1.0 the faulty invocation also dispatches outside its authority scope. C3: a stale configuration version is read inside a long conversation, and later turns still carry it after the source is fixed: session-wide taint, the hard case for precise blocking. N2: a single bad output read by one downstream agent that commands a device. N3: a corrupted root plan that reaches every downstream agent. rand-n7-s0-s2: three random seven-agent DAG workflows from the simulator’s generator; rand-n63-s0 scales the same generator to 63 agents across 16, 32, and 63 logical site daemons on two hosts (Table F.1). HomeSvc and the meeting-room application are detailed in Sections 2 and 5.2.

Alert timing. Controlled comparison grids trigger identical ground-truth alerts naming the faulty origin at fixed wall-clock delays (Table D.1) after faulty output production (early, before downstream readers consume it) or after the last reader starts (late; 20 s after the injected calendar read in the meeting-room application). From this origin alert, AIR-LOCK traces GPG_P forward online to determine reachable taint, select containment switches, and preserve healthy branches. Dedicated grids evaluate EdgeCitadel’s built-in authority and resource boundary detectors without injected alerts (Section 5.5) and symptom-only backward root-cause narrowing (Appendix § 15). Configured delays scale with each grid’s execution time scale (time scale 2 for the workflow, system-comparison, and detector grids; time scale 1 for HomeSvc).

Simulation

The discrete-event simulator executes the same containment controller code over generated multi-agent workflows. It models scheduled effect deadlines, additive action costs, and seeded rogue propagation over a single time-ordered event log (so inter-site journal ingestion lag does not arise; unless marked realistic, control latencies use stress settings).

Broad topology and spread sweeps. Across 24,266 runs over the random-workflow sweep and C2, zero tainted protected effects committed after confirmed containment (0 in the random sweep, 0 on C2). In a paired 2,700-run batch comparing optimized cut and full quarantine across spread regimes, under rogue spread (1,860 runs) optimized cut changes clean rate by +0.91 percentage points (95% CI +0.48 to +1.34) and kept work by −0.76 points (95% CI −1.00 to −0.52); without rogue spread (840 runs), both settings achieve identical clean rates in all 840 runs. Comparing Exit guard against optimized cut over the same batch, Exit guard matches optimized cut’s clean outcome in 839 of 840 non-rogue runs, while under rogue spread Exit guard trails optimized cut by −5.3 points in clean rate and −6.2 points in kept work (narrowing to +0.26 clean and −0.12 kept work when paired with egress revocation). In the HomeSvc scenario under realistic latency at the early alert, pricing tainted replies at zero causes optimized cut to block the tainted schedule read (0% tainted reads, 0 wrong replies, 100% of requests answered across all 120 paired runs, matching Reject source), whereas crediting tainted replies as kept work yields 13,556 wrong replies.

Comparison with the 63-agent scaled testbed (H12-sim). Because the simulator’s single event log assumes instantaneous journal visibility, H12-sim predicted that all paired runs at 32 sites would be clean after the alert; on the two-host testbed, centralized SQLite journal ingestion lag caused 0 of 10 runs to remain clean (Table F.1, Appendix § 19).

Cost Model, Scaling, Case Study, and Scope

Cost model and budget-aware pricing. The cut objective c(a)c(a) is an additive proxy for collateral disruption; safety is independent of c(a)c(a) (Theorem 5), whereas work retention among valid cuts depends on how well c(a)c(a) reflects downstream compute. Across the main grid, optimized cut achieves 100% median kept work (zero lost healthy tasks in the vast majority of runs) because whenever fine-grained artifact or effect holds (priced at the base floor c0c_0) suffice to sever tainted paths, the solver selects them over broad agent pauses or revocations. Because most runs cluster at (c0,0(c_0, 0 lost compute)), variance compression under the default live-work heuristic yields a modest overall Spearman rank correlation of 0.13 (95% bootstrap CI −0.03 to 0.28 across 172 cut runs; 0.28 for action count). In the few runs where healthy tasks are lost (51 of optimized cut’s 57 lost tasks), the loss arises from three structural factors in the live-work heuristic: (i) it prices a credential revocation only by currently running healthy invocations of that agent, so revoking a temporarily idle agent that has future planned tasks or pending hand-offs is priced at c0c_0; (ii) holding a scheduled effect whose issuer has already finished stops no live invocation and is priced at c0c_0; and (iii) conservatively chaining an agent’s invocations within a request marks downstream healthy invocations as tainted and prices pausing them at c0c_0. Pricing revocations instead by an agent’s expected work within its remaining resource budget (bounded by planned tasks) raises the per-run Spearman correlation with lost compute in an offline check to 0.7 (0.72 on optimized cut), cleanly separating zero-loss c0c_0 actions (0 lost tasks across 527 revocations) from higher-disruption revocations (110 of 115 lost tasks across 72 revocations priced >1> 1).

Coordinator ingestion scaling. Across our three-host workflow and smart-home grids (§5.2–§5.4), AIRLOCK converges with sub-second τ1\tau_1 at native latency (21 90th percentile on the main grid) and zero post-τ1\tau_1 safety leaks. To isolate the scaling bottleneck of a single-process SQLite coordinator, we stress-tested a 63-agent workflow across 16, 32, and 63 logical site daemons on two hosts (Table F.1). Even at 63 sites, laminar max-flow solving (0.022–0.031 ms) and per-site action confirmation (39–38 ms median) remain fast, pinpointing centralized single-process SQLite journal ingestion as the sole bottleneck (median ingest lag 42.1 s to 71.6 s at 16 sites, 33.2 s to 67.7 s at 32 sites, and 50.9 s to 62.6 s at 63 sites). Under this overload, AIRLOCK’s fail-closed contract holds—the controller marks un-ingested alerts as INDETERMINATE, never falsely claims τ1\tau_1 (0 of 22 runs), and releases 0 holds prematurely—while effects that commit before their upstream journals arrive cannot be intercepted (1 of 22 runs clean after the alert), motivating sharded journal ingestion for larger clusters.

Multi-agent coding collaboration case study. We additionally evaluated AIRLOCK in observe mode on a live multi-agent document-revision workflow with three third-party CLI coding agents: OpenAI Codex and Google Antigravity CLI as reviewers and Claude Code as author, coordinating through an append-only board and a versioned document store with gateway-mediated publication as the protected sink. When a lagging store replica served a stale document version to a reviewer three times, the controller opened 3 incidents and in all 3 cases selected a single hold on the pending board publication (5–8 ms decision latency, 0.022–0.031 ms laminar max-flow solve, 59863 ms ahead of the publication deadline), with runtime mediation overhead of 3.2%–9.1% of reviewer CLI time and 0.5%–0.8% of author CLI time (median hop 516 ms). The case study also highlights two operational boundaries that motivate future work: because provenance tracks data exposure rather than semantic influence (11 of 22 board entries marked tainted from 3 stale-text writes) and incidents do not automatically clear when an agent reads a tainted artifact to repair it (23 re-solves during repair), practical human-in-the-loop workflows benefit from explicit post-incident endorsement to declassify repaired artifacts.

Prototype scope. Consistent with Theorem 5 (Table A.2), AIRLOCK contains external side effects online rather than rolling back internal agent memory: in HomeSvc, optimized cut blocks all tainted lamp actuations and answers ≥96%\ge96\% of user requests (with 100% correct replies and 0 wrong replies in simulation when tainted replies are priced at zero so the schedule read is blocked, Appendix § 18), whereas once the assistant’s shared memory has ingested the corrupted schedule (0 correct replies in late-alert runs, Table 1), restoring uncontaminated text replies requires pairing AIRLOCK with or no control uses them for that. Fences before an effect exist only in process, as per-call hooks, approvals and per-node interrupts; none sits at the actuator. Stopping work already under way is mostly cooperative; only killing a process (an AutoGen executor, an MCP server) is forced. Recovery relies on checkpoint rollback, replay, or state restore, which re-executes subsequent nodes rather than containing in-flight downstream side effects online.

FrameworkStop or cancelFence before an effectEffects already under wayRollback or replay
A2A 1.0.x, a2a-sdk 1.2.3 [1]Cancel one task; no cancel-all (the operator lists and cancels tasks per server)None for the operator; an agent may reject a task itselfCancellation is attempted, “but success is not guaranteed”None
LangGraph 1.2.16 [23]Cancel a run (interrupt), also in bulkinterrupt() or interrupt-before/after per node; edit the state, then resumeStops the run’s worker; a tool call may have startedRollback of graph state; time travel re-runs every later node
AutoGen 0.7.5 [26]Cancellation token per run; termination conditions after the current turn; stop the runtimeApproval of code execution; an intervention handler can drop a message before deliveryAsync tools are cancelled and code executors killed; sync tools and the current message finishSave and load of state
CrewAI 1.15.28 [6]No stop or cancel; time and iteration limitsBefore-tool-call hook (other hook errors fail open)Guardrails and human review run after executionCheckpoints; replay re-runs every later task
OpenAI Agents SDK 0.24.0 [33]Cancel a streamed run, now or after the turn; turn limitTool approval; tool input guardrail (function tools only); blocking input guardrailAsync tools are cancelled at their next await; sync tools are not stoppedRestore of run state or session history
MCP 2026-07-28, SDK 2.3.0 [28]Cancel a request or a taskThe host confirms tool calls; consent is advisoryThe receiver may ignore a cancel and “is not obligated to actually stop the work”None (stateless)
Semantic Kernel 1.45.0 [27]Cancel an orchestration (experimental); stop the runtimeFunction invocation filter; an intervention handler can drop a messageAgents that already received messages continue; the current message finishesSnapshot and restore of process state

Table G.1. Native containment controls of agent frameworks and protocols, from official documentation and released SDKs. None tracks or acts on downstream consumers of a faulty output.

16 sites32 sites63 sites
Runs6106
Runs reaching τ1\tau_1000
Clean after the alert100
Tainted effects after the alert95911
Decision latency (s)0.45 (0.61)0.40 (0.58)0.43 (14.59*)
Confirmation latency (ms)39 (308)37 (141)38 (111)
Control messages287236284
Ingest lag (s)26.7–35.3 (80.6)32.5–70.0 (90.9)52.4–90.8 (116.0)
Kept work (mean)0.890.920.98

Table F.1. 63-agent scaling stress test across 16, 32, and 63 logical sites on two hosts (optimized cut, H12). Decision: alert to first decision, median (max). Confirmation: per-run median, median over runs (max 95th percentile). Ingest lag: per-run median journal lag from site to coordinator, range (max). *Includes one deferred alert (0.48 s without it).

thogonal memory or checkpoint rollback. Enforced containment covers channels mediated through EDGECITADEL’s site daemons and gateway.

Native Controls of Agent Frameworks

Table G.1 summarizes what each framework offers an operator. Beyond stopping everything, controls act on one call, message, task, run or handoff edge, and none finds the consumers of a bad output: CrewAI’s task context declares inputs, and traces and checkpoint histories exist, but

References

  1. [1]A2A Project. Agent2Agent (A2A) protocol specification and Python SDK (a2a-sdk 1.2.3). https://a2a-protocol.org/, 2026.
  2. [2]Birgisson, A., Politz, J. G., Erlingsson, Ú., Taly, A., Vrable, M., and Lentzner, M. Macaroons: Cookies with contextual caveats for decentralized authorization in the cloud. In Network and Distributed System Security Symposium (NDSS), 2014.DOI
  3. [3]Cemri, M., Pan, M. Z., Yang, S., Agrawal, L. A., Chopra, B., Tiwari, R., Keutzer, K., Parameswaran, A., Klein, D., Ramchandran, K., Zaharia, M., Gonzalez, J. E., and Stoica, I. Why do multi-agent LLM systems fail? In Advances in Neural Information Processing Systems (NeurIPS), 2025.arxiv.org/abs/2503.13657
  4. [4]Costa, M., Köpf, B., Kolluri, A., Paverd, A., Russinovich, M., Salem, A., Tople, S., Wutschitz, L., and Zanella-Béguelin, S. Securing AI agents with information-flow control, 2025. URL https://arxiv.org/abs/2505.23643. arXiv:2505.23643.
  5. [5]Coudert, D., Datta, P., Pérennes, S., Rivano, H., and Voge, M.-E. Shared risk resource group: Complexity and approximability issues. Parallel Processing Letters, 17(2):169–184, 2007.
  6. [6]CrewAI. CrewAI 1.15.28. https://docs.crewai.com, 2026.
  7. [7]Debenedetti, E., Shumailov, I., Fan, T., Hayes, J., Carlini, N., Fabian, D., Kern, C., Shi, C., Terzis, A., and Tramèr, F. Defeating prompt injections by design, 2025. URL https://arxiv.org/abs/2503.18813. arXiv:2503.18813.
  8. [8]Deochake, S. Heartbeat-bound hierarchical credentials: Cryptographic revocation for AI agent swarms, 2026. URL https://arxiv.org/abs/2605.20704. arXiv:2605.20704.
  9. [9]Dinur, I. and Steurer, D. Analytical approach to parallel repetition. In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC), 2014.arxiv.org/abs/1305.1979
  10. [10]Feige, U. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, 1998.
  11. [11]Fellows, M. R., Guo, J., and Kanj, I. The parameterized complexity of some minimum label problems. Journal of Computer and System Sciences, 2010. doi: 10.1016/j.jcss.2010.02.012.DOI
  12. [12]Forough, J., Bhuyan, M., and Elmroth, E. Anomaly detection and resolution on the edge: Solutions and future directions. In 2023 IEEE International Conference on Service-Oriented System Engineering (SOSE), pp. 227–238. IEEE, 2023. doi: 10.1109/SOSE58276.2023.00034.
  13. [14]Goel, A., Po, K., Farhadi, K., Li, Z., and de Lara, E. The Taser intrusion recovery system. In Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP), 2005.
  14. [15]Greenblatt, R., Cotra, A., and Wijk, H. Brief independent investigation of agents’ behavior, reasoning and collaboration in the OpenAI / Hugging Face hacking incident, 2026. URL https://metr.org/blog/2026-08-26-openai-hugging-face-incident-investigation/. METR blog post, 26 August 2026.
  15. [16]Home Assistant. Home Assistant: Open source home automation. https://www.home-assistant.io/, 2026. Accessed: 2026-10-30.
  16. [17]Huang, J.-T., Zhou, J., Jin, T., Zhou, X., Chen, Z., Wang, W., Yuan, Y., Lyu, M. R., and Sap, M. On the resilience of LLM-based multi-agent collaboration with faulty agents. In Proceedings of the 42nd International Conference on Machine Learning (ICML), pp. 26202–26226, 2025.arxiv.org/abs/2408.00989
  17. [18]Huangfu, Q. and Hall, J. A. J. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119–142, 2018.arxiv.org/abs/1503.01889
  18. [19]Jha, S., Sheyner, O., and Wing, J. Two formal analyses of attack graphs. In Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW), 2002.DOI
  19. [20]Khan, S. Stop means stop: Measuring and repairing the enforcement gap in agent-framework control primitives, 2026. URL https://arxiv.org/abs/2607.14166. arXiv:2607.14166.
  20. [21]Kim, T., Wang, X., Zeldovich, N., and Kaashoek, M. F. Intrusion recovery using selective re-execution. In 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 89–104, 2010.DOI
  21. [22]King, S. T. and Chen, P. M. Backtracking intrusions. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP), 2003.
  22. [23]LangChain. LangGraph 1.2.16. https://github.com/langchain-ai/langgraph, 2026.
  23. [25]Liu, L., Yu, H., and Jiang, X. VERA: Authority-preserving edge revocation for federated AI-agent workflows, 2026. URL https://arxiv.org/abs/2608.30091. arXiv:2608.30091.
  24. [26]Microsoft. AutoGen 0.7.5 (agentchat, core, ext). https://github.com/microsoft/autogen, 2026a.
  25. [27]Microsoft. Semantic Kernel 1.45.0. https://learn.microsoft.com/en-us/semantic-kernel/, 2026b.
  26. [28]Model Context Protocol. Model Context Protocol specification, revision 2026-07-28, and Python SDK 2.3.0. https://modelcontextprotocol.io/specification/2026-07-28, 2026.
  27. [29]Mohammadi, B., Potamitis, N., Klein, L., Arora, A., and Bindschaedler, L. Atomix: Timely, transactional tool use for reliable agentic workflows, 2026. URL https://arxiv.org/abs/2602.14849. arXiv:2602.14849.
  28. [30]Muruaga, X. Bounded agents: Delegation security for multi-agent AI systems, 2026. URL https://arxiv.org/abs/2608.15888. arXiv:2608.15888.
  29. [31]NATS Authors. NATS and JetStream. https://nats.io, 2026.
  30. [32]OpenAI. OpenAI–Hugging Face incident technical report. Technical report, OpenAI, 2026a. URL https://cdn.openai.com/pdf/67869394-cb91-4c12-888c-5cbd85c7814c/OpenAI-Hugging-Face2020Incident-Technical-Report.pdf.
  31. [33]OpenAI. OpenAI Agents SDK 0.24.0. https://openai.github.io/openai-agents-python/, 2026b.
  32. [34]Patil, S. G., Zhang, T., Fang, V., Noppapon C., Huang, R., Hao, A., Casado, M., Gonzalez, J. E., Popa, R. A., and Stoica, I. GoEX: Perspectives and designs towards a runtime for autonomous LLM applications, 2024. URL https://arxiv.org/abs/2404.06921. arXiv:2404.06921.
  33. [35]Prakash, S. AIP: Agent identity protocol for verifiable delegation across MCP and A2A, 2026. URL https://arxiv.org/abs/2603.24775. arXiv:2603.24775.
  34. [36]Saltzer, J. H. and Schroeder, M. D. The protection of information in computer systems. Proceedings of the IEEE, 63(9):1278–1308, 1975.DOI
  35. [37]Syros, G., Suri, A., Ginesin, J., Nita-Rotaru, C., and Oprea, A. SAGA: A security architecture for governing AI agentic systems. In Network and Distributed System Security Symposium (NDSS), 2026.arxiv.org/abs/2504.21034
  36. [38]Wang, S., Zhang, G., Yu, M., Wan, G., Meng, F., Guo, C., Wang, K., and Wang, Y. G-Safeguard: A topology-guided security lens and treatment on LLM-based multi-agent systems. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (ACL), pp. 7261–7276, 2025. doi: 10.18653/v1/2025.acl-long.359.DOI
  37. [39]Wang, Y., Yu, C., Zhang, J., Duan, Y., Zheng, M., Wu, Z., Shi, K., and Cai, T. From faulty memories to corrected actions: Dependency-guided rollback repair for memory-augmented agents, 2026. URL https://arxiv.org/abs/2608.10502. arXiv:2608.10502.
  38. [40]Xie, Y., Zhu, C., Zhang, X., Zhu, T., Ye, D., Qi, M., Chen, H., and Zhou, W. From spark to fire: Modeling and mitigating error cascades in LLM-based multi-agent collaboration, 2026. URL https://arxiv.org/abs/2603.04474. arXiv:2603.04474.
  39. [41]Zhan, Z., Li, K., Zhang, Y., and Haddadi, H. HearthNet: Edge multi-agent orchestration for smart homes, 2026a. URL https://arxiv.org/abs/2604.09618. arXiv:2604.09618.
  40. [42]Zhan, Z., Zhang, Y., and Haddadi, H. Poster: EdgeCitadel - Hybrid NATS-MQTT orchestration for edge multi-agent systems. In Companion of the 2026 ACM International Conference on Mobile Systems, Applications, and Services, MobiSys Companion ’26, pp. 43–44, New York, NY, USA, 2026b. Association for Computing Machinery. ISBN 979840027115. doi: 10.1145/3812835.3814871. URL https://doi.org/10.1145/3812835.3814871.
  41. [43]Zhang, P., Cai, J.-Y., Tang, L.-Q., and Zhao, W.-B. Approximation and hardness results for label cut and related problems. Journal of Combinatorial Optimization, 21(2):192–208, 2011.
  42. [44]Zhou, J., Wang, L., and Yang, X. GUARDIAN: Safeguarding LLM multi-agent collaborations with temporal graph modeling. In Advances in Neural Information Processing Systems (NeurIPS), 2025.arxiv.org/abs/2505.19234
  43. [45]Zhu, G. and Wang, C. Authorization revocation for long-running AI agents: Root-scoped quiescence under delegation and asynchronous execution, 2026. URL https://arxiv.org/abs/2609.21284. arXiv:2609.21284.

Paper details

vlnc:W_85ynyzd2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents