TFR-GNN: Topology- and Fault-Aware Graph Neural Scheduling for Heterogeneous Distributed Computing Systems

Shiyu Yang; Ziyang Zeng; Jie-Si Yang

Source-linked AI summary

TFR-GNN: Topology- and Fault-Aware Graph Neural Scheduling for Heterogeneous Distributed Computing Systems

Shiyu Yang, Ziyang Zeng, Jie-Si Yang

arXiv:2609.09165v1Jul 8, 2026cs.DC

TL;DR

Heterogeneous DAG scheduling is NP-hard, and failure-blind placement can perform poorly when machine reliability varies. TFR-GNN combines topology- and fault-aware attention with distillation from a fault-tolerant heuristic portfolio, achieving strong cross-regime results as one policy.

Problem
Heterogeneous DAG scheduling is NP-hard, while fixed makespan-oriented heuristics do not account for failures whose impact depends on reliability, failure intensity, and cluster load.
Method
TFR-GNN uses DAG and machine-topology attention with failure-gated reliability and optional replication, trained by distilling a best-of-portfolio fault-tolerant oracle.
Results
Across real workflows, TFR-GNN matches HEFT without failures, reduces expected makespan under failures by 14.8% on average versus HEFT, and matches a per-scenario hindsight oracle as one policy.
Takeaways & Limitations
A single policy can adapt across failure and load regimes while preserving the trusted HEFT behavior when failures are absent.
Takeaways & Limitations
Results rely on an event-level simulator and Poisson crash, log-normal repair, and restart-in-place assumptions; permanent loss and checkpointing remain future fault models.

Abstract

from arXiv · show

Scheduling workflow directed acyclic graphs (DAGs) on heterogeneous distributed systems is a classical NP-hard problem, and the list-scheduling heuristic HEFT remains the defacto standard because of its low complexity and strong makespan. In real deployments, however, machines fail: commodity and pre-emptible nodes are far less reliable than dedicated ones, and a makespan-optimal but reliability-agnostic placement can be dramatically slowed by node failures. We show empirically, on real workflow structures from the WfCommons/Pegasus corpus, that no single fixed heuristic is best across the joint space of failure intensity and cluster load: with no failures HEFT is optimal, whereas under failures a reliability-aware placement can reduce the expected makespan by up to 52% when spare capacity exists. Motivated by this, we present TFR-GNN, a graph neural scheduler that combines bidirectional dependency attention over the task DAG, topology attention over the (bandwidth-weighted) machine graph, and a cross-attention placement head augmented with a failure-gated reliability tilt and an optional replication gate. We train TFR-GNN by distilling a best-of-portfolio fault-tolerant oracle into a single one-shot policy. On real workflows and a bimodal-reliability cluster model, TFR-GNN matches HEFT exactly when there are no failures, reduces the expected makespan under failures by 14.8% on average (up to 47%) over HEFT, beats a fixed reliability-aware baseline (R-HEFT) by 11% and matches a per-scenario hindsight oracle as a single policy without any deployment-time tuning, and generalises to unseen applications and to workflows an order of magnitude larger than those seen in training, while producing schedules in well under a second for graphs of nearly 5,000 tasks. All results are produced by a verified event-level simulator on real workflow data; no experimental numbers are synthetic.

1 Introduction

Workflow scheduling on heterogeneous systems is NP-hard, and HEFT’s failure-free objective can become fragile when machine reliability varies. TFR-GNN adapts across failure and load regimes by distilling fault-tolerant heuristics into a topology- and fault-aware policy.

Problem: Scheduling assigns DAG tasks to heterogeneous machines while minimizing completion time, making the classical problem NP-hard.HEFT remains the de-facto baseline because it is simple and competitive on makespan.
Motivation: The best policy depends jointly on failure intensity and cluster load: HEFT is optimal without failures, whereas reliability-aware placement improves makespan by up to 52% with spare capacity.With tight capacity, gains shrink and selective replication can help.
Contributions: TFR-GNN combines bidirectional DAG attention, bandwidth-weighted machine-topology attention, and task–machine cross-attention with failure-gated reliability and optional replication mechanisms.The failure gate makes fault-tolerance mechanisms vanish at zero failure intensity, reducing the policy to min-EFT/HEFT.
Training: A best-of-portfolio oracle distils HEFT, reliability-aware, and replication-based heuristics into one adaptive policy without deployment-time scenario tuning.This approach is motivated by policy-gradient training failing to discover coordinated reliability-aware placements on a modest budget.
Evaluation: The evaluation uses real WfCommons/Pegasus workflows and a verified event-level simulator rather than synthetic experimental numbers.The study also covers ablations, sensitivity, unseen applications, larger workflows, and scalability.

2 Related Work

Prior work spans list scheduling, fault-tolerance heuristics, learning-based scheduling, and attention architectures. TFR-GNN combines these strands while targeting reliability-aware scheduling on heterogeneous, non-uniform platforms.

List scheduling: HEFT and CPOP established classical heterogeneous DAG list scheduling, while PEFT adds optimistic look-ahead without changing O(v^2p) complexity.HEFT ranks tasks by upward rank and greedily minimizes earliest finish time.
Fault tolerance: Fault-tolerant scheduling uses replication or reliability-aware placement, but the appropriate balance depends on operating conditions.Replication adds computation and contention; reliability-aware placement trades some speed for fewer restarts.
Learning-based scheduling: Learning-based schedulers such as Decima show that GNN policies can match or exceed hand-tuned heuristics, but TFR-GNN targets fault tolerance on heterogeneous machines rather than homogeneous-cluster throughput.The paper also reports that naive policy gradients are inadequate for this setting.
GNNs and attention: TFR-GNN applies graph attention to the machine graph with a bandwidth bias and distils a portfolio of scheduling heuristics into a compact student.Its reinforcement-learning comparisons include REINFORCE, self-critical training, RLOO, and PPO.

3 Problem Formulation

The formulation schedules a workflow DAG onto heterogeneous, bandwidth-connected machines under stochastic failures and optional replication. Its objective is expected makespan, with the speed–reliability trade-off governed by failure intensity and spare capacity.

3.1 Workflow and platform model: A workflow is a DAG G = (V, E) whose tasks have work and types, while data-bearing edges impose transfer requirements.The platform contains heterogeneous machines with task-dependent speeds and affinities.
3.1 Workflow and platform model: Machine computation costs depend on relative speed and task-type affinity, making processor suitability heterogeneous.Each machine has a relative speed and per-type affinity.
3.1 Workflow and platform model: Inter-machine communication depends on bandwidth and latency, with high intra-rack and low inter-rack bandwidth.This is the related-machines communication model underlying HEFT.
3.2 Bimodal reliability: Machines fail as Poisson processes with log-normal repair, and failed tasks lose partial progress before restarting.Reliability is bimodal and independent of speed, separating volatile and reliable machines.
3.3 Schedule and objective: A schedule specifies task priorities and a primary machine, with optional replicas, and the simulator records makespan, wasted work, and redundant work.Execution follows non-insertion list scheduling under sampled failure traces.
3.3 Schedule and objective: The optimization objective is to minimize expected makespan over failure traces, subject to an optional replication budget.Replication is limited to a maximum fraction of tasks.
3.3 Schedule and objective: At zero failure intensity the problem reduces to classical makespan minimization, whereas positive failure intensity requires balancing speed against reliability.The balance also depends on available spare capacity.

4 The TFR-GNN Scheduler

TFR-GNN combines DAG and machine-topology attention with failure-aware placement and guided decoding. It is trained by distilling a best-of-portfolio oracle into a single adaptive policy while preserving HEFT behavior without failures.

Architecture: TFR-GNN fuses dependency attention, topology attention, cross-attention placement, and fault-aware mechanisms into a one-pass scheduler.A linear-time greedy decode converts predicted priorities and placement scores into a schedule.
Architecture: Bidirectional DAG attention captures ancestor and descendant structure, while bandwidth-biased machine attention represents communication-aware heterogeneity.Task embeddings use directed graph attention; machine embeddings use log-bandwidth biases.
Fault-aware placement: A failure-activity gate makes reliability tilting and replication disappear at zero failure intensity, reducing placement to min-EFT/HEFT exactly.The placement bias is therefore an architectural adaptivity guarantee rather than a learned approximation.
Guided decoding: The scheduler uses guided list decoding that places ready tasks using priorities, placement bias, evolving earliest-finish times, and optional replication decisions.The placement score selects machines through the guided decode, while newly ready successors enter the ready set.
Training by distillation: Policy-gradient training was ineffective because HEFT is a strong local optimum and sampled perturbations were generally worse, motivating oracle distillation.RLOO stabilized near 1.00×HEFT, but sampled policies remained 20–45% worse than HEFT.
Training by distillation: Distillation runs HEFT, reliability-aware, and replication-based heuristics over failure traces, then trains TFR-GNN to imitate the best expected-makespan choice.Training uses teacher-forced placement and replication losses, with scenarios sampled across cluster sizes, failure scales, and replication budgets.

5 Experimental Setup

The evaluation uses real WfCommons/Pegasus workflows, heterogeneous bimodal-reliability clusters, and verified CPU-only simulation. It compares TFR-GNN with classical, reliability-aware, replication-based, and oracle baselines using failure-free and failure-aware metrics.

Workloads: The dataset contains 135 real workflow instances from seven applications, with four applications for training and three held out for cross-application testing.Instance sizes range from 22 to 4,000 tasks.
Cluster instantiation: Clusters vary machine speeds, task affinities, rack bandwidth, and bimodal reliability, with volatile machines sampled independently of speed.The default model assigns 35% of machines volatile spot-like reliability.
Baselines: The comparison includes HEFT, CPOP, PEFT, Min-Min, Max-Min, Random, fixed and scenario-best R-HEFT, replication-based FT-HEFT, and a best-of-portfolio oracle.R-HEFT uses reliability tilts, while FT-HEFT duplicates high-risk tasks within a budget.
Metrics: Failure-aware evaluation estimates expected makespan over 40 independent failure traces using common random numbers and reports confidence intervals, wasted work, redundant work, and generation time.Failure-free evaluation reports makespan relative to HEFT and machine utilisation.
Reproducibility: The implementation uses a verified Python/PyTorch simulator on one CPU core, fixes random seeds, and regenerates results from released workflow data.The trained model has 62,870 parameters and requires only a few gigabytes of RAM.

6 Results

Across failure-free and failure-prone settings, TFR-GNN preserves HEFT’s baseline performance while adapting toward reliability-aware schedules that approach the hindsight oracle.

1.000× relative makespan and 0.832 utilisation: TFR-GNN matches HEFT exactly without failures and outperforms PEFT, Min-Min, Max-Min, CPOP, and Random.
12–22% lower expected makespan under failures: TFR-GNN beats fixed R-HEFT and replication-based FT-HEFT while matching the hindsight Oracle without scenario tuning.Averaged over s > 0, TFR-GNN reaches 0.852×HEFT versus the Oracle’s 0.854×.
2% to 40% gains as cluster size increases from M=16 to M=96 at s=2, showing stronger benefits when spare capacity is available.The average gain is 14.5%, with a best case of 0.529×HEFT.

6.4 Placement vs. replication

TFR-GNN favors reliability-aware placement over indiscriminate replication in the evaluated fault model, while its architectural components jointly support the gains.

Lower expected makespan with zero redundant computation: TFR-GNN outperforms FT-HEFT, whose redundant computation reaches 23% of the HEFT makespan-equivalent.The learned replication gate abstains because restarted volatile-node tasks eventually complete and backups rarely offset contention.
0.853 full-model expected makespan versus 0.934 without the fault-aware head, making that head the largest ablation loss.Removing dependency, cross-, or topology attention costs 3–4%, and all variants match HEFT at s=0.
40% gain at M=96: increasing spare capacity strengthens TFR-GNN’s advantage over HEFT at fixed s=2.

6.6 Sensitivity analysis

Sensitivity and generalisation tests show that TFR-GNN retains its advantage across heterogeneity, volatility, applications, and larger workflows, with gains depending on reliable spare machines.

0.88–0.94×HEFT across machine heterogeneity, while gains emerge with volatility and level off when too few reliable machines remain.At ρ=0, TFR-GNN matches HEFT at 0.999 because no volatile machines create an avoidance opportunity.
0.593×HEFT at s=2 on the unseen soykb application, a 41% reduction, while TFR-GNN matches HEFT at s=0 and generally beats R-HEFT.

6.8 Scalability

TFR-GNN combines fast one-pass schedule generation with architectural and training choices that preserve performance across operating regimes.

701 ms for a 4,846-task workflow versus HEFT’s 387 ms, keeping schedule generation under a second and within the same order of magnitude.PEFT is one to two orders of magnitude slower and is evaluated only up to 800 tasks.
Every architectural component contributes, with the fault-aware head providing the largest improvement in the ablation.
At zero volatility TFR-GNN matches HEFT, while gains grow with volatility and spare capacity.
Distillation loss decreases and converges within minutes on one CPU, whereas reinforcement-learning attempts drift or stall at HEFT.

7 Discussion and Limitations

TFR-GNN adapts reliability-aware scheduling while preserving HEFT behavior when failures are absent, but its conclusions remain bounded by simulation and modeled fault assumptions.

Discussion: The failure-activity gate enables an exact reduction to HEFT when there is nothing to be robust to, avoiding failure-free cost.
Limitations: The evaluation uses an event-level simulator driven by real workflow structures and runtimes, so production effects such as contention and stragglers are not fully captured.
Limitations: The modeled Poisson crashes, log-normal repair, and restart-in-place favor reliability-aware placement over replication, limiting conclusions about permanent loss or checkpointing.Exploring those fault models is identified as future work.
Discussion: Schedules remain well under a second for workflows of nearly 5,000 tasks, with generation time measured on a single CPU.Table 6 reports schedule-generation time by workflow size and notes that PEFT was not evaluated above 800 tasks.

8 Conclusion

The paper presents TFR-GNN as a topology- and fault-aware scheduler for heterogeneous distributed systems. On real workflows, it preserves HEFT performance without failures while improving expected makespan under failures and scaling to larger workloads.

Conclusion: TFR-GNN combines dependency and topology attention with failure-gated reliability and optional replication mechanisms, trained by distilling a fault-tolerant oracle.
Conclusion: TFR-GNN matches HEFT exactly without failures and reduces expected makespan under failures by 14.8% on average, up to 47%.It also beats a fixed reliability-aware baseline by approximately 11% and matches a per-scenario hindsight oracle as a single policy.
Conclusion: The scheduler generalises to unseen applications and workflows an order of magnitude larger than training workloads while producing schedules in well under a second.All reported numbers are computed by simulation on real workflow data.