PaperlayerView exact revision on arXiv

Source-linked AI summary

Schedule Repair for DAG Workflows under Link Disruptions

Mohammadali Khodabandehlou, Jared Coleman, Bhaskar Krishnamachari, Kevin Chan

arXiv:2609.34048v1cs.DC

TL;DR

Link disruptions can invalidate DAG workflow schedules planned for stable networks, while already-started tasks and in-flight transfers constrain what can be changed. The paper compares four repair scopes and prices repair by decision latency proportional to moved tasks. No scope wins across disruption types: the preferred response varies with disruption structure, workload, and repair cost.

  • Problem

    DAG workflow schedules assume a stable network, but mobility, interference, and jamming can invalidate links after tasks start and transfers are underway.

    Source: §I · p. 1

  • Method

    The paper compares waiting, rerouting, local repair, and global repair against an oracle, charging decision latency proportional to the number of moved tasks.

    Source: §I · p. 1

  • Results

    No single repair scope wins: rerouting nearly erases isolated failures that cost 30% waiting, while global repair comes within 4% of the oracle under jamming blackouts.

    Source: §I · p. 1

  • Takeaways & Limitations

    Repair scope should match disruption correlation, persistence, and price; when uncertain, reacting less can avoid chasing network states that no longer hold.

    Source: §VI · p. 6

    The model excludes disseminating new assignments over the same disrupted network, leaving that cost for future work on decentralized repair.

    Source: §III · p. 3

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper asks how much of a DAG workflow schedule should move when a link disruption invalidates it, and argues that the right repair scope depends on disruption structure and repair cost. It evaluates a spectrum of repair policies and finds that no single scope wins.

I. INTRODUCTION

  • DAG schedules assume a stable network, but mobility, interference, and jamming can invalidate links after tasks have committed and transfers are already sunk or lost costs.The remaining decision is how much of the pending schedule to change.Source: §I · p. 1
  • The paper compares repair policies of increasing scope against an oracle that knows the disruption trace in advance.The workload is fixed while the network changes, unlike prior work on how arrivals displace previously placed tasks.Source: §I · p. 1
  • The repair ladder gives policies shared disruption semantics and charges decision latency proportional to the number of tasks moved while the old schedule continues executing.The paper also builds four disruption generators with different correlation structures.Source: §I · p. 1
  • Across 500 variants, repair scope must match disruption structure and communication regime: rerouting nearly erases isolated failures that cost 30% waiting, while global repair comes within 4% of the oracle under jamming blackouts.Waiting is favored under memoryless flapping for larger and communication-heavy workloads; self-healing mobility outages reward patience, and repair latency erodes large scopes first.Source: §I · p. 1
  • The evaluation spans 100 workload instances from synthetic structures, RIoTBench pipelines, and WfCommons workflows, each at five communication-to-computation ratios.The work is implemented in ncsim [5] with deterministic, seed-reproducible runs.Source: §I · p. 1

II. RELATED WORK

Prior workflow fault tolerance commonly provisions redundancy for processor failures, whereas this paper considers reactive repair after wireless link disruptions without spare capacity.

A. Fault-Tolerant Workflow Scheduling

  • Traditional workflow fault tolerance replicates or checkpoints tasks so processor failures cost re-execution rather than a lost workflow.Mei et al. reschedule tasks suspended by resource failures and tolerate an arbitrary number of failures.Source: A. Fault-Tolerant Workflow Scheduling · p. 1
  • Prior approaches generally address processor failures in wired datacenters or grids and provision spare capacity before failure.The passage identifies VMs, cluster nodes, and grid sites as examples of failing components.Source: A. Fault-Tolerant Workflow Scheduling · p. 1
  • This setting instead treats wireless links as the failing component, with no spare capacity and a reactive schedule repair after disruption is observed.The pending schedule is repaired rather than relying on pre-provisioned redundancy.Source: A. Fault-Tolerant Workflow Scheduling · pp. 1–2

B. Reactive Rescheduling and Failure-Resilient Edge Scheduling

Related work studies reactive rescheduling, network repair, and dynamic wireless scheduling, but does not compare repair scope for compute task-graph schedules under link disruptions.

B. Reactive Rescheduling and Failure-Resilient Edge Scheduling

  • Prior reactive rescheduling triggers on delay beyond schedule slack or runtime estimate deviations, while edge-server failure work uses one fixed policy for dependent tasks.Workload-dynamics studies limit replanning to recent graphs,; this paper instead asks how much of a schedule should move when the platform changes and workload remains fixed.Source: B. Reactive Rescheduling and… · p. 2

C. Repair in Networks

  • Networking provides local and global repair precedents, while Pozo et al. repair TDMA transmission schedules locally; their computation placements do not move.This paper applies the local-versus-global question to task placement on heterogeneous nodes, optimizing makespan rather than frame-set schedulability.Source: C. Repair in Networks · p. 2

D. Scheduling in Dynamic Wireless Environments

  • Dynamic wireless offloading targets arriving, mostly independent tasks under channel uncertainty, while bursty links and mobility lifetimes have established models used here as trace generators,,.Jupiter copes with degraded links but does not study repair policy; networked-compute simulators have treated the network as stable [5].Source: D. Scheduling in Dynamic Wireless… · p. 2
  • The authors identify no prior comparison of repair scopes for compute task-graph schedules under link-level disruptions or study of how scope depends on disruption statistics.The surrounding work addresses jamming-aware offloading, link behavior models,,, and related scheduling or simulation settings, [5].Source: D. Scheduling in Dynamic Wireless… · p. 2

III. SYSTEM MODEL

The system models DAG execution across heterogeneous compute nodes connected by bandwidth-limited radio links. Disruptions can interrupt transfers and trigger replanning of pending tasks, with repair latency charged according to moved-task count.

III. SYSTEM MODEL

  • Radio links connect compute nodes with heterogeneous speeds; nodes execute one task at a time, and concurrent transfers share link bandwidth fairly.Source: §III · p. 2
  • Task-graph dependencies carry data between placed tasks, and execution is event-driven as inputs arrive and nodes become free.Source: §III · p. 2
  • A failed-link transfer is aborted and retransmitted in full; stalled transfers wait for recovery or repair, while started tasks remain committed.Source: §III · p. 2
  • Replanning takes effect after a decision-latency window proportional to moved tasks; the old schedule continues during that window, and dissemination over the disrupted network is excluded.Source: §III · pp. 2–3

A. The Repair Ladder

The repair ladder compares policies that differ in how many pending tasks they may move after a disruption. Its oracle is a foresight reference using HEFT, not a globally optimal scheduler.

A. The Repair Ladder

  • Repair scope is the set of pending tasks a policy may move, and the ladder orders policies by increasing scope.Source: A. The Repair Ladder · p. 3
  • Wait moves nothing and retries stalled transfers after link recovery; reroute uses multi-hop detours without moving tasks.Source: A. The Repair Ladder · p. 3
  • Local repair replans reached tasks and their pending descendants, leaving all other pending tasks pinned.Source: A. The Repair Ladder · p. 3
  • Global repair replans every pending task against the disrupted network.Source: A. The Repair Ladder · p. 3
  • The oracle sees the full trace but still places tasks with HEFT; both rescheduling policies use HEFT, so their difference is scope rather than placement quality.Source: A. The Repair Ladder · p. 3

IV. DISRUPTION MODELS

Four disruption generators produce timed link-event traces with intentionally different correlation structures. The scheduler observes events as they occur, while only the oracle knows the full trace.

IV. DISRUPTION MODELS

  • All four processes compile to timed link-event traces, enabling comparison under identical workloads and policies despite different correlation structures.Source: §IV · p. 3
  • The generators model connectivity and bandwidth disruptions, not attacks that compromise nodes, alter task execution, falsify scheduler state, or target the control plane.Source: §IV · p. 3
  • Single failure is the controlled case: one radio pair fails at a chosen time for a chosen duration.Source: §IV · p. 3
  • Memoryless flapping independently alternates exponential up and down times across radio pairs, producing short, unannounced outages.Source: §IV · p. 3
  • Mobility creates temporally correlated degradation as nodes move, with links recovering when nodes approach again.Source: §IV · p. 3
  • Jamming abruptly severs every radio pair in range and restores them when it stops; at this deployment scale, it creates a total blackout.Source: §IV · p. 3

A. Setup

The evaluation implements the repair and disruption semantics in ncsim and tests workload families across five communication-to-computation ratios. Disruption processes are parameterized relative to undisrupted makespan, and reported aggregates pool across the grid unless a figure resolves CCR.

A. Setup

  • The study runs 500 variants: 100 workload instances across synthetic, RIoTBench, and WfCommons structures, each tested at five CCR values.Source: A. Setup · p. 3
  • Workloads run on five-node heterogeneous networks with full-mesh radio links; CCR ranges from 0.2 to 5, spanning compute-bound to communication-bound instances.Source: A. Setup · p. 3
  • Disruptions are scaled to undisrupted makespan M0: single failures last 0.5M0, jamming lasts 0.6M0, and flapping and mobility use M0-relative parameters.Source: A. Setup · p. 3
  • Fig. 1 contrasts link-state traces across isolated failure, independent flapping, self-healing mobility, and an all-link jamming blackout.Source: Figure 1 · p. 4
  • For the illustrated episode, waiting finishes at 1.50 × M0, local repair at 1.01 × M0, and global repair at 0.99 × M0.Source: Figure 2 · p. 4
  • Single-failure aggregates include only biting cases, while the three stochastic processes remain pooled; outcomes are geometric-mean makespan ratios over the oracle.Source: A. Setup · p. 4

B. Results

The results show that disruption effects depend on where traffic meets an outage, and that repair scope and cost change the relative makespan outcomes. The figures resolve policies by communication regime and repair cost, while Table I reports outcomes by workload family.

1) Where and when a failure bites:

  • 22 of 90 pair–time cells were affected in one representative CCR 1 instance, exactly where planned traffic met the outage window.Rerouting nearly erases the damage a detour can, local repair caps the worst waiting outcomes, and global repair can benefit from re-optimizing the original placement.Source: 1) Where and when a failure bites · p. 4
  • At CCR 1 in one representative instance, outages affected 22 of 90 pair–time cells; rerouting erased nearly all damage a detour could, while local repair capped the worst cells that waiting paid dearly for.Under flapping, rerouting is best at CCR ≤0.5 but falls to 2.7× the oracle at CCR 5, where waiting wins.Source: 1) Where and when a failure bites · p. 4, Figure 3 · p. 5
  • At δ = 0, the largest repair scope is favored, but by δ = 0.2–0.5 both repair scopes converge onto the waiting line under every process.Wait and reroute move no tasks, so their references do not vary with repair cost.Source: Figure 4 · p. 5

B. Results

  • Table I reports geometric-mean makespan over the oracle by workload family at zero repair cost.The caption identifies the best policy in bold.Source: Table I · p. 5

2) The best scope tracks the disruption structure:

The best repair scope varies with disruption structure, communication regime, and workload scale. Broad blackouts favor global repair, while transient flapping and self-healing mobility can favor less reaction.

2) The best scope tracks the disruption structure:

  • Under jamming, global repair comes within 4% of the oracle and local repair within 8%, while waiting gives up 13% and rerouting 26%.Under flapping, waiting at 1.13 beats rescheduling and rerouting because the short outages end before repair consequences do.Source: 2) The best scope tracks the… · p. 5
  • For isolated failures, rerouting nearly erases the damage on biting cells at 1.05, while waiting reaches 1.31; under self-healing mobility, waiting and rerouting beat both repair scopes.Mobility outages self-heal as departed nodes return, so reacting can move tasks toward nodes about to leave.Source: 2) The best scope tracks the… · p. 5

3) The communication regime amplifies, and can flip, the verdict:

  • Under flapping, rerouting is best through CCR 0.5 but reaches 2.7× the oracle at CCR 5, where waiting wins.Repeated aborts discard entire transfers that remain on the air long enough to encounter another flap; jamming favors global repair at every CCR.Source: 3) The communication regime amplifies,… · p. 5

4) Workload scale shifts the optimum down the ladder:

  • On small RIoTBench pipelines of about 10 tasks, global repair leads under every stochastic process, but on 45–102-task WfCommons workflows, waiting decisively beats reactions under flapping.Synthetic structures fall between those workload families, with global repair best or tied under stochastic processes.Source: 4) Workload scale shifts the optimum… · p. 6

5) Repair latency erodes large scopes first:

Repair latency erodes the advantage of moving more tasks, and the paper concludes that scope should be matched to disruption structure and repair cost. The conclusion also identifies control-plane and warning assumptions that remain open.

5) Repair latency erodes large scopes first:

  • By δ = 0.2–0.5, both repair scopes converge onto waiting under every process, and repair is not worthwhile at any price under flapping or mobility.At δ = 0.02M0 per moved task, local repair matches or beats global repair under single failure and jamming; expensive repair can also damp flapping churn as newer plans supersede pending ones.Source: 5) Repair latency erodes large scopes… · p. 6

6) The design ladder:

  • The design ladder recommends waiting for short or self-healing disruptions, rerouting isolated persistent failures, local repair for localized or costly repairs and large workloads, and global repair for broad, correlated, persistent outages.Rising repair costs or communication intensity push cases toward smaller scopes.Source: 6) The design ladder · p. 6

VI. CONCLUSION

  • The evaluation assumes link-state observation and out-of-band plan dissemination; feasible repair during a blackout needs a separate control channel or decentralized repair, and proactive repair before forecast mobility outages remains open.The out-of-band assumption is strongest where global repair wins.Source: §VI · p. 6
Loading 2609.34048v1…