# Bounding the Response Time of DAG Tasks Using Long Paths

arXiv: https://arxiv.org/abs/2211.08800 · HTML: https://mlsanity.com/paper/2211.08800/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2022.

## Built on by (most cited first, 2 of 2)

- [RED: A Systematic Real-Time Scheduling Approach for Robotic Environmental Dynamics](https://mlsanity.com/paper/2308.15368/) (2023)
- [Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning](https://mlsanity.com/paper/2308.14647/) (2023)

## Abstract (arXiv)

In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.