# Reservation-Based Federated Scheduling for Parallel Real-Time Tasks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2017.

## 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)
- [Strict Partitioning for Sporadic Rigid Gang Tasks](https://mlsanity.com/paper/2403.10726/) (2024)

## Abstract (arXiv)

This paper considers the scheduling of parallel real-time tasks with arbitrary-deadlines. Each job of a parallel task is described as a directed acyclic graph (DAG). In contrast to prior work in this area, where decomposition-based scheduling algorithms are proposed based on the DAG-structure and inter-task interference is analyzed as self-suspending behavior, this paper generalizes the federated scheduling approach. We propose a reservation-based algorithm, called reservation-based federated scheduling, that dominates federated scheduling. We provide general constraints for the design of such systems and prove that reservation-based federated scheduling has a constant speedup factor with respect to any optimal DAG task scheduler. Furthermore, the presented algorithm can be used in conjunction with any scheduler and scheduling analysis suitable for ordinary arbitrary-deadline sporadic task sets, i.e., without parallelism.