Pontus Ekberg
Senior Lecturer/Associate Professor at Department of Information Technology; Division of Computer Systems
- Telephone:
- +46 18 471 73 41
- E-mail:
- pontus.ekberg@it.uu.se
- Visiting address:
- Hus 10, Regementsvägen 10
- Postal address:
- Box 337
751 05 UPPSALA
- Academic merits:
- Docent
Short presentation
I study algorithms and computational problems, mainly in real-time scheduling theory.
Please see my personal web page for more information.
Keywords
- algorithms
- scheduling theory

Publications
Selection of publications
Fixed-Parameter Analysis of Preemptive Uniprocessor Scheduling Problems
Part of 2022 IEEE Real-Time Systems Symposium (RTSS 2022), p. 185-196, 2022
Partitioned Scheduling of Recurrent Real-Time Tasks
Part of 2021 IEEE Real-Time Systems Symposium (RTSS), p. 356-367, 2021
Rate-Monotonic Schedulability of Implicit-Deadline Tasks is NP-hard Beyond Liu and Layland's Bound
Part of 2020 IEEE Real-Time Systems Symposium (RTSS), p. 308-318, 2020
Dual Priority Scheduling is Not Optimal
Part of Leibniz International Proceedings in Informatics (LIPIcs), 2019
- DOI for Dual Priority Scheduling is Not Optimal
- Download full text (pdf) of Dual Priority Scheduling is Not Optimal
Fixed-Priority Schedulability of Sporadic Tasks on Uniprocessors is NP-hard
Part of 2017 IEEE Real-Time Systems Symposium (RTSS), p. 139-146, 2017
Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete
Part of Proc. 27th Euromicro Conference on Real-Time Systems, p. 281-286, 2015
Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization
Part of Proc. 36th Real-Time Systems Symposium, p. 87-95, 2015
Recent publications
Learning-assisted schedulability analysis: opportunities and limitations
Part of Real-time systems, p. 332-358, 2025
Part of Proceedings of the 33rd International Conference on Real-Time Networks and Systems (RTNS), 2025
A Closer Look at Pseudo-polynomial Time and Its Use in Real-Time Scheduling Theory
Part of Real time and such, p. 120-134, Springer Nature, 2025
The Safe and Effective Use of Optimistic Period Predictions
Part of 2024 32ND INTERNATIONAL CONFERENCE ON REAL-TIME NETWORKS AND SYSTEMS, RTNS 2024, p. 197-206, 2024
- DOI for The Safe and Effective Use of Optimistic Period Predictions
- Download full text (pdf) of The Safe and Effective Use of Optimistic Period Predictions
A Closer Look at Pseudo-polynomial Time and Its Use in Real-Time Scheduling Theory
Part of Lecture Notes in Computer Science, 2024
All publications
Articles in journal
Learning-assisted schedulability analysis: opportunities and limitations
Part of Real-time systems, p. 332-358, 2025
Optimal Scheduling of Measurement-Based Parallel Real-Time Tasks
Part of Real-time systems, p. 247-253, 2020
- DOI for Optimal Scheduling of Measurement-Based Parallel Real-Time Tasks
- Download full text (pdf) of Optimal Scheduling of Measurement-Based Parallel Real-Time Tasks
Uniprocessor scheduling of real-time synchronous dataflow tasks
Part of Real-time systems, p. 1-31, 2019
Schedulability analysis of a graph-based task model for mixed-criticality systems
Part of Real-time systems, p. 1-37, 2016
An optimal resource sharing protocol for generalized multiframe tasks
Part of The Journal of logical and algebraic methods in programming, p. 92-105, 2015
- DOI for An optimal resource sharing protocol for generalized multiframe tasks
- Download full text (pdf) of An optimal resource sharing protocol for generalized multiframe tasks
Bounding and shaping the demand of generalized mixed-criticality sporadic task systems
Part of Real-time systems, p. 48-86, 2014
- DOI for Bounding and shaping the demand of generalized mixed-criticality sporadic task systems
- Download full text (pdf) of Bounding and shaping the demand of generalized mixed-criticality sporadic task systems
The fork-join real-time task model
Part of ACM SIGBED Review, p. 20-20, 2013
- DOI for The fork-join real-time task model
- Download full text (pdf) of The fork-join real-time task model
Chapters in book
A Closer Look at Pseudo-polynomial Time and Its Use in Real-Time Scheduling Theory
Part of Real time and such, p. 120-134, Springer Nature, 2025
Comprehensive doctoral thesis
Conference papers
Part of Proceedings of the 33rd International Conference on Real-Time Networks and Systems (RTNS), 2025
The Safe and Effective Use of Optimistic Period Predictions
Part of 2024 32ND INTERNATIONAL CONFERENCE ON REAL-TIME NETWORKS AND SYSTEMS, RTNS 2024, p. 197-206, 2024
- DOI for The Safe and Effective Use of Optimistic Period Predictions
- Download full text (pdf) of The Safe and Effective Use of Optimistic Period Predictions
A Closer Look at Pseudo-polynomial Time and Its Use in Real-Time Scheduling Theory
Part of Lecture Notes in Computer Science, 2024
Using Deep Learning for Schedulability Verification in Safety-Critical Systems
2024
Who’s Afraid of Butterflies? A Close Examination of the Butterfly Attack
Part of Proceedings of the 44th IEEE Real-Time Systems Symposium (RTSS), 2023
Elastic Scheduling for Harmonic Task Systems
Part of 2024 IEEE 30TH REAL-TIME AND EMBEDDED TECHNOLOGY AND APPLICATIONS SYMPOSIUM, RTAS 2024, p. 334-347, 2023
Efficient Explainability of Real-Time Schedulability
2023
Rethinking Tractability for Schedulability Analysis
Part of Proceedings of the 44th IEEE Real-Time Systems Symposium (RTSS), p. 1-12, 2023
Towards Efficient Explainability of Schedulability Properties in Real-Time Systems
Part of Proceedings of the 35th Euromicro Conference on Real-Time Systems (ECRTS), 2023
Fixed-Parameter Analysis of Preemptive Uniprocessor Scheduling Problems
Part of 2022 IEEE Real-Time Systems Symposium (RTSS 2022), p. 185-196, 2022
Certificates of Real-Time Schedulability
2022
Complexity of partitioned scheduling for periodic tasks
2022
Partitioned Scheduling of Recurrent Real-Time Tasks
Part of 2021 IEEE Real-Time Systems Symposium (RTSS), p. 356-367, 2021
Graceful Degradation in Semi-Clairvoyant Scheduling
Part of 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021), 2021
- DOI for Graceful Degradation in Semi-Clairvoyant Scheduling
- Download full text (pdf) of Graceful Degradation in Semi-Clairvoyant Scheduling
Rate-Monotonic Schedulability of Implicit-Deadline Tasks is NP-hard Beyond Liu and Layland's Bound
Part of 2020 IEEE Real-Time Systems Symposium (RTSS), p. 308-318, 2020
Dual Priority Scheduling is Not Optimal
Part of Leibniz International Proceedings in Informatics (LIPIcs), 2019
- DOI for Dual Priority Scheduling is Not Optimal
- Download full text (pdf) of Dual Priority Scheduling is Not Optimal
Fixed-Priority Schedulability of Sporadic Tasks on Uniprocessors is NP-hard
Part of 2017 IEEE Real-Time Systems Symposium (RTSS), p. 139-146, 2017
Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation
2017
Refinement of workload models for engine controllers by state space partitioning
Part of 29th Euromicro Conference on Real-Time Systems, 2017
Multiprocessor Real-Time Locking Protocols for Replicated Resources
Part of Proc. 28th Euromicro Conference on Real-Time Systems (ECRTS), p. 50-60, 2016
On fixed-priority schedulability analysis of sporadic tasks with self-suspension
Part of Proc. 24th International Conference on Real-Time Networks and Systems, p. 109-118, 2016
Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete
Part of Proc. 27th Euromicro Conference on Real-Time Systems, p. 281-286, 2015
Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization
Part of Proc. 36th Real-Time Systems Symposium, p. 87-95, 2015
Bounding and shaping the demand of mixed-criticality sporadic tasks
Part of Proc. 24th Euromicro Conference on Real-Time Systems, p. 135-144, 2012
Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems
Part of Proc. Real-Time Systems Symposium, p. 13-23, 2011
Resource sharing protocols for real-time task graph systems
Part of Proc. 23rd Euromicro Conference on Real-Time Systems, p. 272-281, 2011
On the tractability of digraph-based task models
Part of Proc. 23rd Euromicro Conference on Real-Time Systems, p. 162-171, 2011
A distributed swarm-intelligent localization for sensor networks with mobile nodes
Part of Proc. 7th International Wireless Communications and Mobile Computing Conference, p. 83-88, 2011
The digraph real-time task model
Part of 17th Real-Time and Embedded Technology and Applications Symposium, p. 71-80, 2011