CS Paper Radar

Schedule Repair for DAG Workflows under Link Disruptions

Mohammadali Khodabandehlou, Jared Coleman, Bhaskar Krishnamachari, Kevin Chan

cs.DC ·submitted 2026-09-28 00:17 UTC · v1

Abstract

Schedules for directed acyclic graph (DAG) workflows in networked IoT systems are typically computed assuming a static or generally stable network. In contested and adversarial environments, this assumption is not valid. Links degrade and fail due to mobility, interference, and jamming. We study schedule repair: when a link disruption invalidates part of a schedule, how much of it should be rescheduled? We introduce a spectrum of repair policies that vary in repair scope, how much of the pending schedule each may move: wait out the disruption, reroute data around it, reschedule only the affected tasks locally, or reschedule all pending tasks globally. We evaluate each against an oracle and charge every repair a decision latency proportional to the extent to which it moves. Across 100 workload instances spanning synthetic task graphs, RIoTBench pipelines, and WfCommons scientific workflows, each run at five communication-to-computation ratios (CCRs) and disrupted by processes with deliberately different correlation structure, we find that no single scope wins: rerouting nearly erases isolated failures that cost waiting 30%, global repair comes within 4% of the oracle under jamming blackouts, waiting is favored under memoryless link flapping for larger and communication-heavy workloads (the scheduling analog of route-flap damping), self-healing mobility outages reward patience over reaction, and accounting for repair latency erodes large scopes first. We conclude that the scope of the repair should be adapted to the disruption process and the repair cost, rather than fixed by the scheduler.

Comment
6 pages, 4 figures, 1 table. Accepted to the IoTAE Workshop at IEEE MILCOM 2026

Closest papers

Nearest neighbours by meaning across the whole index.

BRIDGE: Selective Boundary Repair with Dependency Graph Evidence in Multi-Agent Systems

cs.CL ·2026-10-13 ·Encheng Su, Pengze Li, Ziheng Hua, Qiucheng Yu, Jianyu Wu +10 more
benchmarkhighly cited similarity 0.64
Abstract

Multi-agent collaboration has emerged as a critical paradigm for tackling complex, long-horizon tasks; however, while coordination protocols continue to advance, systemic failures at the inter-agent collaboration interface remain a pervasive bottleneck. In collaborative workflows, systems frequently suffer from \emph{broken handoffs}---where critical task context is omitted, misrouted, or ignored despite each agent emitting locally plausible responses. To address this challenge, we present \method, a verifiable runtime control framework that treats handoff repair as selective intervention over explicit dependency graphs. Central to \method is an integrated fault-attribution and calibration pipeline, \dataset, which decouples execution dependencies and injects counterfactual handoff perturbations to provide empirical supervision for runtime intervention. Leveraging this diagnostic foundation, \method dynamically compiles observable interaction traces into a provenance graph to pinpoint unresolved dependencies, without accessing private agent states. It then evaluates candidate repairs through an empirical gate that weighs expected gains against disruption risks, and executes repairs only when formal local postconditions hold. Extensive evaluations across demanding benchmarks demonstrate that \method boosts task success by up to 12.3 absolute percentage points on SILO-BENCH and 11.1 on TeamBench. Across both backbones, \method maintains strict cost-effectiveness, adding as little as 2.0\% marginal token overhead. Furthermore, on 562 handoff-relevant traces from the MAST benchmark, \method achieves 69.8\% F1 in a single pass, establishing a reliable operational boundary for verifiable coordination repair.

0.50

Agent Mesh: Reliability Primitives for Non-Idempotent Agent Delegation - Identity Adequacy and Evidence Adequacy

cs.AI cs.DCcs.MAcs.SE ·2026-08-26 ·Mazhar Shaikh, Anurag Rajkumar Bombarde, Harshal Pathak
similarity 0.62
Abstract · 14 pages, 9 figures, 6 tables; 5-page ancillary supplement

Autonomous agents increasingly perform bounded software tasks under an orchestrator that retries, resumes, and budgets them. The machinery such orchestrators reach for is the service mesh's: retry, timeout, and error-rate circuit breaking. We report a failure study of a production agentic software-delivery platform over 147 numbered incidents spanning 81 runs, each with a measured cost and, in most cases, a mutation proof reproducing the failure. All three assumptions those primitives rest on are violated in practice, and we quantify the consequences: a loop of fifty-four consecutive successful tool calls no error-rate breaker could see; a progress signal constant by construction, guaranteeing a false trip on the third repair round and driving one run from six of six components to three; twenty-one events accumulated across six invocations of one delegation, making a correct, idempotent component unwinnable; a misrouted failure that woke five components for a two-component fault, leaving three bystanders regressing working code; and twelve incidents in which the enforcement layer blocked correct work, the most expensive costing 107 agent turns and zero accepted writes. We find one cross-cutting cause and its dual. Identity adequacy: in five separate subsystems an identity that failed to discriminate produced a confident wrong answer, and two of them derived the corrective rule independently. Evidence adequacy: a reliability decision may be taken only on evidence capable of moving, attributable to what it measures, and deterministic under identical conditions. From the findings we derive seven reliability primitives whose enforcement unit is the delegation rather than the message, and specify the controlled evaluation the study motivates but does not constitute.

0.19

FaaSpot: Fault-Tolerant Serverless Workflow Execution on Spot Instances

cs.DC ·2026-10-19 ·Bandhan Patel, Sushruth Harsha, Kwangsung Oh, In Kee Kim
publishedcode/data similarity 0.62
Abstract · 14 pages, 12 figures, 7 tables. To appear in the 27th International Middleware Conference (Middleware '26), December 14-18, 2026, Tarragona,…

Serverless computing is increasingly used to run complex DAG workflows across diverse applications, and individual function execution times have grown to support them, pushing workflow makespans to hours. Open-source serverless platforms, deployed on a pool of VMs, typically use on-demand instances, and their cost increases with the makespan. Spot instances are far cheaper, but a preemption is likely before the workflow finishes. A preemption at a fan-out node or a task feeding a fan-in node stalls every parallel branch, cascading a single preemption into a workflow-wide failure. Prior systems address this challenge by migrating high-impact tasks to reliable, non-spot resources, sacrificing spot's cost advantage. We present FaaSpot, a serverless workflow execution system that runs every workflow task on spot instances with no on-demand fallback. Our key insight is that cascade-prone positions are determined by the DAG's topology and can be identified before execution. Therefore, FaaSpot analyzes the workflow DAG once at submission time and classifies each task by the impact of its preemption. Selective checkpointing, survival-aware scaling, and lineage-based retry then act on this single classification, with no runtime coordination. We evaluate FaaSpot on a trace-driven spot emulator with eight DAG workflows against four state-of-the-art baselines. FaaSpot completes 89.03% of runs at $0.018 per successful run, 21pp (percentage points) above the average baseline success rate and at a lower cost per success than every baseline, while reducing mean latency by 2.3x.

0.52

ArrivalBench: Agent-Generated Data Pipelines Are Correct Once and Wrong Under Time

cs.LG cs.DB ·2026-10-01 ·Pranay Kothari
published similarity 0.61
Abstract · Accepted as a poster at the NeurIPS 2026 Workshop "Who Verifies the Agents?". 20 pages

Benchmarks for agent-generated data work grade a pipeline by running it once against a fixed snapshot. ArrivalBench instead re-executes the pipeline an agent leaves behind under adversarial but replayable delivery schedules (late, duplicated, out-of-order and retried records) and requires its final state to equal a batch recomputation of the complete log. Because the oracle recomputes rather than classifies, a wrong table and a crash are distinct verdicts: a crash is visible to monitoring a team already runs, and a wrong table is not. On 40 tasks we built, our reimplementation of single-execution grading certifies 86-100% of the pipelines eleven models produce; re-executing the same artifacts finds 7.0-79.2% of the certified ones silently wrong. The gap is not produced by the repair loop: within the same model and task, pipelines repaired against the snapshot test fail replay about as often as those that passed it first time. In every model, idempotency hazards fail more often than ordering hazards. Separating a wrong answer from a crash also changes how interventions read: a hazard warning cuts one model's silent failure from 48.2% to 10.5% while raising its crash rate from 9.0% to 37.0%, so all-in failure moves only from 51.0% to 44.0%. All eleven arms were independently re-run, and rates moved by at most 5.9 points.

0.33

Throughput-Optimal Control of Distributed Computing Networks for Service DAGs

cs.NI ·2026-11-03 ·Peng Li, Jianan Zhang, Jaime Llorca, Xinzhe Fu, Xiang Cheng +1 more
similarity 0.61
Abstract

Executing service workflows with directed acyclic graph (DAG) dependencies over wireless distributed computing networks requires joint control of function placement, routing, and scheduling, together with synchronization of inputs from the same request at merge points. We study throughput-optimal control of these networks under stochastic request arrivals, time-varying wireless links, and interference constraints. We use a valid mapping abstraction that assigns each service function to a computation node and each DAG dependency to a routing path. Using this abstraction, we characterize the network capacity region to support service DAGs, and prove that synchronizing the packets of a request at merge points does not shrink the region. We develop Dynamic Computing Network Control for service DAGs (DCNC-DAG), a dynamic control policy that selects queue-aware valid mappings and schedules service DAG execution by nearest-to-origin (NTO) while enforcing input synchronization at merge points. With exact minimum-cost valid mappings, DCNC-DAG is throughput-optimal and ensures rate stability of the physical queues under bounded arrivals. These guarantees hold for any fixed finite interval between mapping updates, even when mapping decisions rely on boundedly stale queue length information. For larger service DAGs, we develop DCNC-DAG-H, which replaces exact mapping optimization with a queue-aware heuristic. Simulations show that DCNC-DAG supports $2.7\times$-$5.5\times$ the throughput of queue-blind baselines, while DCNC-DAG-H achieves up to $2.68\times$ those of the corresponding baselines on larger workflow and AI service DAGs.

0.24

Sustaining In-Network Computation in Satellite Networks: An Architecture for Semantic Continuity

cs.NI cs.DC ·2026-11-14 ·Zhiyuan Ren, Wenchi Cheng
position similarity 0.60
Abstract · 8 pages, 5 figures. Submitted to IEEE Wireless Communications

Satellite computations often outlast the paths and providers initially serving them. We argue that in-network computing should organize changing execution opportunities around one continuing logical computation: workers execute ready operations, while consumers recognize which results already contribute. We present an architecture separating logical computation, stream context, and physical binding, and show in wildfire assessment how retained observations support recomputation while reachable association history stays in place. A 300-node Linux prototype examines placement, dependency assembly, and continuation. Across 120 images, stage-wise placement delivers 82.08% of positions within deadlines versus 76.06% for single-node placement, while traces separate blocked output delivery from dependencies split across providers. Across 50 observations with 20-node isolation, Confirmation-Coordinated Rebinding (CCR) coordinates replanning, source replay, cross-attempt acceptance, and in-band confirmation to complete all 50 observations with verified outputs using seven replays and 13 ignored duplicate outputs.

0.34

When AI Agents Should Repair, Replan, or Abandon: A Threshold Theory of Plan Commitment

cs.AI ·2026-11-14 ·Gaurav Tewari
benchmark similarity 0.60
Abstract · 22 pages, 6 figures, 3 tables

AI agents often discover mid-execution that their plan is broken, for example when an action fails or a tool is withdrawn. Deployed systems use conventions such as retry loops or "always replan," and a recent benchmark finds no fixed strategy dominates. This paper derives the optimal policy. In the model, a disruption destroys the causal support of part of a plan; repair is a partial reset that preserves the plan's structure, replanning is a full reset, and changing a plan is costly because others have conditioned on it. The optimal policy is a threshold in effective disruption depth: repair shallow damage, replan after deep damage, and abandon the goal when even a fresh plan is not worth its cost. Depth depends on plan structure. In expectation, a single broken action forces 1+R(G)/n actions to be revalidated, where R(G) counts the pairs of actions joined by a dependency path; to first order, a fully serial plan switches to replanning at raw damage about w times smaller than a plan of w parallel chains. A closed-form stability-price threshold determines when a worse repaired plan should be kept over a better fresh one. As language-model planners push replanning costs toward zero, the stability price becomes the only force sustaining plan commitment. Under repeated disruptions, revision frictions make commitment hysteresis optimal: the agent keeps executing a plan it would never choose fresh, and each repair adds patch debt until the debt outweighs repair's cost advantage and the agent rebuilds. A value-of-diagnosis result states when measuring damage is worth its compute and shows that "always replan" is optimal when damage is predictably deep and replanning is the better fallback. A separately implemented numerical checker tests each proposition (zero violations; 1.6 million static-model evaluations), and the model's regime map reproduces that benchmark's regime flips qualitatively.

0.14

From Reactive to Agentic Resilience: Multi-Timescale AI-RAN Orchestration Under Signaling Storms

cs.NI cs.AI ·2026-11-02 ·Sotiris Chatzimiltis, Mahdi Boloursaz Mashhadi, Mohammad Shojafar, Rahim Tafazolli
theory similarity 0.59
Abstract · 13 Pages, 9 Figures, 7 Tables. Paper submitted to IEEE for possible publication

Next-generation open radio access network (Open RAN) and AI-RAN deployments turn the RAN into a disaggregated, compute-aware platform whose service continuity depends on many control loops acting at different timescales. Resilience in this setting is best seen as a lifecycle spanning anticipation, absorption, adaptation, recovery, and evolution. Yet, existing mechanisms remain stage-specific and are rarely coordinated across the control hierarchy. This paper argues that agentic AI offers an orchestration layer that coordinates this lifecycle, turning operator intent into coordinated action while keeping slow language-model reasoning off the fast control path. Using mass-attachment signaling storms as a running study, we build a discrete-event Open RAN attach simulator that captures retry amplification, shared-compute contention, and non-instantaneous provisioning, and we propose a three-tier framework in which an orchestrator at the service management and orchestration layer sets a standing policy, a per-site non-real-time agent judges storms and anticipates scheduled crowds, and a deterministic near-real-time loop enforces every decision. Across experiments, the agentic controller approaches the resilience of a fully provisioned pool of servers at a quarter of its capacity by reading a scheduled event from a calendar and provisioning ahead of it. No reactive weight setting recovers this once the surge arrives. Free-text operator intents ground into control directives at 94% exact match on previously unseen intents, and a single instruction reshapes live behavior end to end. We also quantify the latency, cost, and contention limits that bound it. The supplementary material provides analytical proof of the derived Theorem on anticipation horizon, as well as the subsequent Corollary results on reactive provisioning limits.

0.15