DROPS

Document

Improved Elastic Scheduling Algorithms for Implicit-Deadline Tasks

Authors: Marion Sudvarg, Christopher Gill, and Sanjoy Baruah

Published in: LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2

Abstract

Elastic scheduling provides a framework under which the utilizations of recurrent tasks are reduced by increasing their periods in response to system overload. The original elastic scheduling model was proposed by Buttazzo et al. in 1998 for implicit-deadline tasks on a uniprocessor and decreases task utilizations to satisfy a schedulable utilization bound. In 2019, Orr and Baruah extended the framework to multiprocessor scheduling of implicit-deadline tasks. In this paper, we propose, analyze, and evaluate new elastic scheduling algorithms for several of the scheduling policies considered in these prior works. In particular, (i) we evaluate an algorithm that we proposed as a short note in the Real-Time Systems journal and demonstrate that it allows for faster admission control than the algorithm of Buttazzo et al. when applied to uniprocessor and fluid scheduling. (ii) We also present faster elastic scheduling algorithms for partitioned EDF scheduling. Finally, (iii) we provide polynomial-time exact elastic scheduling algorithms for global EDF and global RM.

Cite as

Marion Sudvarg, Christopher Gill, and Sanjoy Baruah. Improved Elastic Scheduling Algorithms for Implicit-Deadline Tasks. In LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2, pp. 2:1-2:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{sudvarg_et_al:LITES.10.2.2,
  author =	{Sudvarg, Marion and Gill, Christopher and Baruah, Sanjoy},
  title =	{{Improved Elastic Scheduling Algorithms for Implicit-Deadline Tasks}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{2:1--2:36},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.2.2},
  URN =		{urn:nbn:de:0030-drops-252346},
  doi =		{10.4230/LITES.10.2.2},
  annote =	{Keywords: real-time systems, elastic scheduling, scheduling algorithms}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2025.12

Real-Time System Evaluation Techniques: A Systematic Mapping Study

Authors: Tilmann L. Unte and Sebastian Altmeyer

Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)

Abstract

A systematic mapping study assesses a broad selection of research publications with the aim of categorizing them according to a research question. We present the first systematic mapping study on evaluation practices within the field of real-time systems, by analyzing publications from the top three conferences ECRTS, RTAS, and RTSS from 2017 until 2024. Our study provides a comprehensive view on the evaluation practices prevalent in our community, including benchmark software, task set and graph generators, case studies, industrial challenges, and custom solutions. Based on our study, we construct and publish a dataset enabling quantitative analysis of evaluation practices within the real-time systems community. Our analysis indicates shortcomings in current practice: custom case studies are abundant, while industrial challenges have very minor impact. Reproducibility has only been shown for a small subset of evaluations and there is no indication of change. Adoption of new and improved tools and benchmarks is very slow or even non-existent. Evaluation must not be viewed as an obligation when publishing a paper, but as a key element in ensuring practicability, comparability, and reproducibility. Based on our study, we conclude that our community currently falls short on these objectives.

Cite as

Tilmann L. Unte and Sebastian Altmeyer. Real-Time System Evaluation Techniques: A Systematic Mapping Study. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{unte_et_al:LIPIcs.ECRTS.2025.12,
  author =	{Unte, Tilmann L. and Altmeyer, Sebastian},
  title =	{{Real-Time System Evaluation Techniques: A Systematic Mapping Study}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-377-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{335},
  editor =	{Mancuso, Renato},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.12},
  URN =		{urn:nbn:de:0030-drops-235903},
  doi =		{10.4230/LIPIcs.ECRTS.2025.12},
  annote =	{Keywords: Systematic Mapping Study, Real-Time Systems, Evaluation}
}

Document

DOI: 10.4230/LIPIcs.CPM.2025.7

FL-RMQ: A Learned Approach to Range Minimum Queries

Authors: Paolo Ferragina and Filippo Lari

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract

We address the problem of designing and implementing a data structure for the Range Minimum Query problem. We show a surprising connection between this classical problem and the geometry of a properly defined set of points in the Cartesian plane. Building on this insight, we hinge upon a well-known result in Computational Geometry to introduce the first RMQ solution that exploits (i.e., learns) the distribution of such 2D-points via proper error-bounded linear approximations. Because of these features, we name the resulting data structure: Fully-Learned RMQ, shortly FL-RMQ. We prove theoretical bounds for its space usage and query time, covering both worst-case scenarios and average-case performance for uniformly distributed inputs. These bounds compare favorably with the ones achievable by the best-known indexing solutions (i.e., the ones that allow access to the indexed array), especially when the input data follow some geometric regularities that we characterize in the paper, thus providing principled evidence of FL-RMQ being a novel data-aware solution to the RMQ problem. We corroborate our theoretical findings with a wide set of experiments showing that FL-RMQ offers more robust space-time trade-offs than the other known practical indexing solutions on both artificial and real-world datasets. We believe that our novel approach to the RMQ problem is noteworthy not only for its interesting space-time trade-offs, but also because it is flexible enough to be applied easily to the encoding variant of RMQ (i.e., the one that does not allow access to the indexed array), and moreover, because it paves the way to research opportunities on possibly other problems.

Cite as

Paolo Ferragina and Filippo Lari. FL-RMQ: A Learned Approach to Range Minimum Queries. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ferragina_et_al:LIPIcs.CPM.2025.7,
  author =	{Ferragina, Paolo and Lari, Filippo},
  title =	{{FL-RMQ: A Learned Approach to Range Minimum Queries}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.7},
  URN =		{urn:nbn:de:0030-drops-231014},
  doi =		{10.4230/LIPIcs.CPM.2025.7},
  annote =	{Keywords: Range-Minimum query, Learned data structures, Compact data structures, Experimental results}
}

Document

Vision

DOI: 10.4230/TGDK.1.1.13

Autonomy in the Age of Knowledge Graphs: Vision and Challenges

Authors: Jean-Paul Calbimonte, Andrei Ciortea, Timotheus Kampik, Simon Mayer, Terry R. Payne, Valentina Tamma, and Antoine Zimmermann

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract

In this position paper, we propose that Knowledge Graphs (KGs) are one of the prime approaches to support the programming of autonomous software systems at the knowledge level. From this viewpoint, we survey how KGs can support different dimensions of autonomy in such systems: For example, the autonomy of systems with respect to their environment, or with respect to organisations; and we discuss related practical and research challenges. We emphasise that KGs need to be able to support systems of autonomous software agents that are themselves highly heterogeneous, which limits how these systems may use KGs. Furthermore, these heterogeneous software agents may populate highly dynamic environments, which implies that they require adaptive KGs. The scale of the envisioned systems - possibly stretching to the size of the Internet - highlights the maintainability of the underlying KGs that need to contain large-scale knowledge, which requires that KGs are maintained jointly by humans and machines. Furthermore, autonomous agents require procedural knowledge, and KGs should hence be explored more towards the provisioning of such knowledge to augment autonomous behaviour. Finally, we highlight the importance of modelling choices, including with respect to the selected abstraction level when modelling and with respect to the provisioning of more expressive constraint languages.

Cite as

Jean-Paul Calbimonte, Andrei Ciortea, Timotheus Kampik, Simon Mayer, Terry R. Payne, Valentina Tamma, and Antoine Zimmermann. Autonomy in the Age of Knowledge Graphs: Vision and Challenges. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{calbimonte_et_al:TGDK.1.1.13,
  author =	{Calbimonte, Jean-Paul and Ciortea, Andrei and Kampik, Timotheus and Mayer, Simon and Payne, Terry R. and Tamma, Valentina and Zimmermann, Antoine},
  title =	{{Autonomy in the Age of Knowledge Graphs: Vision and Challenges}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{13:1--13:22},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.13},
  URN =		{urn:nbn:de:0030-drops-194872},
  doi =		{10.4230/TGDK.1.1.13},
  annote =	{Keywords: Knowledge graphs, Autonomous Systems}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2017.10

Communication Centric Design in Complex Automotive Embedded Systems

Authors: Arne Hamann, Dakshina Dasari, Simon Kramer, Michael Pressler, and Falk Wurst

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract

Automotive embedded applications like the engine management system are composed of multiple functional components that are tightly coupled via numerous communication dependencies and intensive data sharing, while also having real-time requirements. In order to cope with complexity, especially in multi-core settings, various communication mechanisms are used to ensure data consistency and temporal determinism along functional cause-effect chains. However, existing timing analysis methods generally only support very basic communication models that need to be extended to handle the analysis of industry grade problems which involve more complex communication semantics. In this work, we give an overview of communication semantics used in the automotive industry and the different constraints to be considered in the design process. We also propose a method for model transformation to increase the expressiveness of current timing analysis methods enabling them to work with more complex communication semantics. We demonstrate this transformation approach for concrete implementations of two communication semantics, namely, implicit and LET communication. We discuss the impact on end-to-end latencies and communication overheads based on a full blown engine management system.

Cite as

Arne Hamann, Dakshina Dasari, Simon Kramer, Michael Pressler, and Falk Wurst. Communication Centric Design in Complex Automotive Embedded Systems. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hamann_et_al:LIPIcs.ECRTS.2017.10,
  author =	{Hamann, Arne and Dasari, Dakshina and Kramer, Simon and Pressler, Michael and Wurst, Falk},
  title =	{{Communication Centric Design in Complex Automotive Embedded Systems}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.10},
  URN =		{urn:nbn:de:0030-drops-71624},
  doi =		{10.4230/LIPIcs.ECRTS.2017.10},
  annote =	{Keywords: Communication semantics, logical execution time, implicit communication, automotive, embedded systems, scheduling simulation, Amalthea}
}

Document

DOI: 10.4230/LITES-v004-i001-a002

Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results

Authors: Florian Kluge

Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1

Abstract

The concept of a firm real-time task implies the notion of a firm deadline that should not be missed by the jobs of this task. If a deadline miss occurs, the concerned job yields no value to the system. For some applications domains, this restrictive notion can be relaxed. For example, robust control systems can tolerate that single executions of a control loop miss their deadlines, and still yield an acceptable behaviour. Thus, systems can be developed under more optimistic assumptions, e.g. by allowing overloads. However, care must be taken that deadline misses do not accumulate. This restriction can be expressed by the model of (m,k)-firm real-time tasks that require that from any k consecutive jobs at least m are executed successfully. In this article, we extend our prior work on the MKU scheduling heuristic. MKU uses history-cognisant utility functions as means for making decisions in overload situations. We present new theoretical results on MKU and on other schedulers for (m,k)-firm real-time tasks. Based on extensive simulations, we assess the performance of these schedulers. The results allow us to identify task set characteristics that can be used as guidelines for choosing a scheduler for a concrete use case.

Cite as

Florian Kluge. Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 02:1-02:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{kluge:LITES-v004-i001-a002,
  author =	{Kluge, Florian},
  title =	{{Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:25},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a002},
  URN =		{urn:nbn:de:0030-drops-192635},
  doi =		{10.4230/LITES-v004-i001-a002},
  annote =	{Keywords: Real-time Scheduling, (m, k)-Firm Real-Time Tasks}
}

6 Search Results for "Kramer, Simon"

Improved Elastic Scheduling Algorithms for Implicit-Deadline Tasks

Abstract

Cite as

Real-Time System Evaluation Techniques: A Systematic Mapping Study

Abstract

Cite as

FL-RMQ: A Learned Approach to Range Minimum Queries

Abstract

Cite as

Autonomy in the Age of Knowledge Graphs: Vision and Challenges

Abstract

Cite as

Communication Centric Design in Complex Automotive Embedded Systems

Abstract

Cite as

Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results

Abstract

Cite as

Thanks for your feedback!

Could not send message