Feasibility analysis of recurrent DAG tasks is PSPACE-hard

DOI10.1016/J.TCS.2024.115062MaRDI QIDQ7028337zbMATH OpenFDO

Authors Vincenzo Bonifaci, Alberto Marchetti-Spaccamela

Publication date 12 February 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.115062

zbMATH Keywords

computational complexityfeasibility testingparallel computingprecedence constraintsreal-time schedulingsporadic task system

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A survey of hard real-time scheduling for multiprocessor systems
• A survey on real-time DAG scheduling, revisiting the Global-Partitioned Infinity War
• Complexity of Scheduling under Precedence Constraints
• EDF-schedulability of synchronous periodic task systems is coNP-hard
• Feasibility analysis of sporadic real-time multiprocessor task systems
• Feasibility problems for recurring tasks on one processor
• Games against nature
• Global EDF scheduling for parallel real-time tasks
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 7370961 (Why is no real title available?)
• Multiprocessor schedulability of arbitrary-deadline sporadic tasks: complexity and antichain algorithm
• Multiprocessor scheduling for real-time systems
• NP-complete scheduling problems
• Online Algorithms
• Online algorithms. The state of the art
• Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible
• Optimal scheduling for two-processor systems
• Optimal Sequencing of Two Equivalent Processors
• Optimal time-critical scheduling via resource augmentation
• Schedulability Analysis of Conditional Parallel Task Graphs in Multicore Systems
• The NP-completeness column
• Two-Processor Scheduling with Start-Times and Deadlines

This page was built for publication: Feasibility analysis of recurrent DAG tasks is \(\mathsf{PSPACE}\)-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7028337)