51 Search Results for "Baruah, Sanjoy"

Document
DOI: 10.4230/LITES.10.2.1
Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management

Authors: Franco Cordeiro, Samuel Tardieu, and Laurent Pautet

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
Managing actions with uncertain resource costs is a complex challenge, particularly in autonomous robot mission planning. Robots are often assigned multiple objectives with varying criticality levels, ranging from catastrophic to minor impacts, where failures can significantly affect system safety. Uncertainties in worst-case costs of resources, such as energy and operating time - the time it takes to carry out an action - further complicate mission planning and execution. Monte Carlo Tree Search (MCTS) is a powerful tool for online planning, yet it struggles to account for uncertainty in worst-case cost estimations. Optimistic estimates risk resource shortages, while pessimistic ones lead to inefficient allocation. The Mixed-Criticality (MC) approach, originally developed for real-time systems to schedule critical tasks by allocating processing resources under Worst-Case Execution Time (WCET) uncertainty, provides a framework of rules, models and design principles. We claim this framework can be adapted to autonomous robot mission planning, where critical objectives are met through analogous allocation of different kinds of resources such as energy and operating time despite uncertainties. We propose enhancing MCTS with MC principles to handle uncertainty in worst-case costs across multiple resources and criticality of objectives. High-critical objectives must always be completed, regardless of resource constraints, while low-critical objectives operate flexibly, consuming resources within optimistic estimates when possible or being discarded when resources become scarce. This ensures efficient resource reallocation and prioritization of high-critical objectives. To implement this, we present (MC)²TS, a novel variant of MCTS that integrates MC principles for dynamic resource management. It supports more than two criticality levels to ensure that the most critical components meet the most stringent safety and reliability requirements, while also enabling robust resource management. By enabling replanning and mode changes, (MC)²TS improves MCTS’s efficiency and enhances MC systems’ adaptability to both degrading and improving resource conditions. We evaluate (MC)²TS in an active perception scenario, where a drone retrieves data from distributed sensors under unpredictable environmental conditions. (MC)²TS outperforms MCTS by achieving more objectives, adapting plans when costs drop. It explores more objective sequences, minimizes oversizing, and enhances efficiency. Balancing safety and performance, it monitors robot battery, mission and objective resource constraints such as deadlines. Its robustness ensures low-critical objectives do not compromise high-critical objectives, making it a reliable solution for complex systems characterized by uncertain resource costs and critical objectives.
Cite as

Franco Cordeiro, Samuel Tardieu, and Laurent Pautet. Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management. In LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{cordeiro_et_al:LITES.10.2.1,
  author =	{Cordeiro, Franco and Tardieu, Samuel and Pautet, Laurent},
  title =	{{Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:23},
  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.1},
  URN =		{urn:nbn:de:0030-drops-252339},
  doi =		{10.4230/LITES.10.2.1},
  annote =	{Keywords: Embedded Systems, Safety / Mixed-Critical Systems, Real-Time Systems, Energy Aware Systems}
}
Document
DOI: 10.4230/LITES.10.2.2
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/LITES.10.1.4
Revisiting Slot-Shifting’s Offline Acceptance Test for Sporadic Tasks: A Technical Note

Authors: Mohammad Ibrahim Alkoudsi, Damir Isovic, and Gerhard Fohler

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

Abstract
The Slot-Shifting algorithm presents a solution to combine the benefits of offline and online scheduling in time-triggered systems. It dynamically adjusts the allocation of time slots to tasks in the scheduling tables to accommodate aperiodic tasks at runtime. In this note, we revisit an extension to Slot-Shifting that enables it to handle sporadic task sets. In particular, we clarify the assumptions required for the correct application of its offline acceptance test, identify sources of pessimism within it, and address its schedulability analysis interval.
Cite as

Mohammad Ibrahim Alkoudsi, Damir Isovic, and Gerhard Fohler. Revisiting Slot-Shifting’s Offline Acceptance Test for Sporadic Tasks: A Technical Note. In LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1, pp. 4:1-4:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{alkoudsi_et_al:LITES.10.1.4,
  author =	{Alkoudsi, Mohammad Ibrahim and Isovic, Damir and Fohler, Gerhard},
  title =	{{Revisiting Slot-Shifting’s Offline Acceptance Test for Sporadic Tasks: A Technical Note}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{4:1--4:6},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.1.4},
  URN =		{urn:nbn:de:0030-drops-252354},
  doi =		{10.4230/LITES.10.1.4},
  annote =	{Keywords: real-time systems scheduling, time-triggered systems, offline acceptance test of sporadic tasks}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.5
RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality

Authors: Franco Cordeiro, Samuel Tardieu, and Laurent Pautet

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

Abstract
Robot planning in distributed systems, such as drone fleets performing active perception missions, presents complex challenges. These missions require cooperation to achieve objectives like collecting sensor data or capturing images. Multi-robot systems offer significant advantages, including faster execution and increased robustness, as robots can compensate for individual failures. However, resource costs, affected by environmental factors such as wind or terrain, are highly uncertain, impacting battery consumption and overall performance. Mission objectives are often prioritized by criticality, such as retrieving data from low-battery sensors to prevent data loss. Addressing these priorities requires sophisticated scheduling to navigate high-dimensional state-action spaces. While heuristics are useful for approximating solutions, few approaches extend to multi-robot systems or adequately address cost uncertainty and criticality, particularly during replanning. The Mixed-Criticality (MC) paradigm, extensively studied in real-time scheduling, provides a framework for handling cost uncertainty by ensuring the completion of high-critical tasks. Despite its potential, the application of MC in distributed systems remains limited. To address the decision-making challenges faced by distributed robots operating under cost uncertainty and objective criticality, we propose four contributions: a comprehensive model integrating criticality, uncertainty, and robustness; distributed synchronization and replanning mechanisms; the incorporation of mixed-criticality principles into multi-robot systems; and enhanced resilience against robot failures. We evaluated our solution, named RESCUE, in a simulated scenario and show how it increases the robustness by reducing the oversizing of the system and completing up to 40% more objectives. We found an increase in resilience of the multi-robot system as our solution not only guaranteed the safe return of every non-faulty robot, but also reduced the effects of a faulty robot by up to 14%. We also computed the performance gain compared to using MCTS in a single robot of up to 2.31 for 5 robots.
Cite as

Franco Cordeiro, Samuel Tardieu, and Laurent Pautet. RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cordeiro_et_al:LIPIcs.ECRTS.2025.5,
  author =	{Cordeiro, Franco and Tardieu, Samuel and Pautet, Laurent},
  title =	{{RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{5:1--5:23},
  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.5},
  URN =		{urn:nbn:de:0030-drops-235835},
  doi =		{10.4230/LIPIcs.ECRTS.2025.5},
  annote =	{Keywords: Multi-Robot Systems, Embedded Systems, Safety/Mixed-Critical Systems, Real-Time Systems, Monte-Carlo Tree Search}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.2
Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems

Authors: Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo

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

Abstract
Memory bandwidth regulation and cache partitioning are widely used techniques for achieving predictable timing in real-time computing systems. Combined with partitioned scheduling, these methods require careful co-allocation of tasks and resources to cores, as task execution times strongly depend on available allocated resources. To address this challenge, this paper presents a 0-1 linear program for task-resource co-allocation, along with a multi-objective heuristic designed to minimize resource usage while guaranteeing schedulability under a preemptive EDF scheduling policy. Our heuristic employs a multi-layer framework, where an outer layer explores resource allocations using Pareto-pruned search, and an inner layer optimizes task allocation by solving a knapsack problem using dynamic programming. To evaluate the performance of the proposed optimization algorithm, we profile real-world benchmarks on an embedded AMD UltraScale+ ZCU102 platform, with fine-grained resource partitioning enabled by the Jailhouse hypervisor, leveraging cache set partitioning and MemGuard for memory bandwidth regulation. Experiments based on the benchmarking results show that the proposed 0-1 linear program outperforms existing mixed-integer programs by finding more optimal solutions within the same time limit. Moreover, the proposed multi-objective multi-layer heuristic performs consistently better than the state-of-the-art multi-resource-task co-allocation algorithm in terms of schedulability, resource usage, number of non-dominated solutions, and computational efficiency.
Cite as

Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo. Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ECRTS.2025.2,
  author =	{Sun, Binqi and Wei, Zhihang and Bastoni, Andrea and Roy, Debayan and Theile, Mirco and Kloda, Tomasz and Pellizzoni, Rodolfo and Caccamo, Marco},
  title =	{{Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{2:1--2:23},
  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.2},
  URN =		{urn:nbn:de:0030-drops-235807},
  doi =		{10.4230/LIPIcs.ECRTS.2025.2},
  annote =	{Keywords: Multi-objective optimization, memory bandwidth regulation, cache partitioning, partitioned scheduling, real-time systems}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.3
Enabling Containerisation of Distributed Applications with Real-Time Constraints

Authors: Nasim Samimi, Luca Abeni, Daniel Casini, Mauro Marinoni, Twan Basten, Mitra Nasri, Marc Geilen, and Alessandro Biondi

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

Abstract
Containerisation is becoming a cornerstone of modern distributed systems, thanks to their lightweight virtualisation, high portability, and seamless integration with orchestration tools such as Kubernetes. The usage of containers has also gained traction in real-time cyber-physical systems, such as software-defined vehicles, which are characterised by strict timing requirements to ensure safety and performance. Nevertheless, ensuring real-time execution of co-located containers is challenging because of mutual interference due to the sharing of the same processing hardware. Existing parallel computing frameworks such as Ray and its Kubernetes-enabled variant, KubeRay, excel in distributed computation but lack support for scheduling policies that allow guaranteeing real-time timing constraints and CPU resource isolation between containers, such as the SCHED_DEADLINE policy of Linux. To fill this gap, this paper extends Ray to support real-time containers that leverage SCHED_DEADLINE. To this end, we propose KubeDeadline, a novel, modular Kubernetes extension to support SCHED_DEADLINE. We evaluate our approach through extensive experiments, using synthetic workloads and a case study based on the MobileNet and EfficientNet deep neural networks. Our evaluation shows that KubeDeadline ensures deadline compliance in all synthetic workloads, adds minimal deployment overhead (in the order of milliseconds), and achieves lower worst-case response times, up to 4 times lower, than vanilla Kubernetes under background interference.
Cite as

Nasim Samimi, Luca Abeni, Daniel Casini, Mauro Marinoni, Twan Basten, Mitra Nasri, Marc Geilen, and Alessandro Biondi. Enabling Containerisation of Distributed Applications with Real-Time Constraints. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 3:1-3:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{samimi_et_al:LIPIcs.ECRTS.2025.3,
  author =	{Samimi, Nasim and Abeni, Luca and Casini, Daniel and Marinoni, Mauro and Basten, Twan and Nasri, Mitra and Geilen, Marc and Biondi, Alessandro},
  title =	{{Enabling Containerisation of Distributed Applications with Real-Time Constraints}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{3:1--3:29},
  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.3},
  URN =		{urn:nbn:de:0030-drops-235816},
  doi =		{10.4230/LIPIcs.ECRTS.2025.3},
  annote =	{Keywords: Kubernetes, real-time containers, SCHED\underlineDEADLINE, KubeRay}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.7
Period Assignment for Real-Time Cascade Control Tasks Under Stability and Schedulability Constraints

Authors: Ismail Hawila, Liliana Cucu-Grosjean, and Slim Ben Amor

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

Abstract
Existing results for cyber-physical systems have been proposed to merge the requirements associated to the stability of the physical components and the schedulability of the cyber components. Nevertheless, none of the existing results has studied these requirements for multiple real-time cascade control tasks where their periods choice are dependent and affect stability. In this paper, we propose a methodology to evaluate the periods of the real-time cascade control tasks that ensures stability of the physical components, then we present a co-design problem for the period choice that guarantees good performance of the physical components and schedulability of the cyber components under fixed-priority scheduling. We then evaluate this methodology on a real use-case of a drone system. Results show the importance of studying these requirements together as their relation has an impact on stable periods range.
Cite as

Ismail Hawila, Liliana Cucu-Grosjean, and Slim Ben Amor. Period Assignment for Real-Time Cascade Control Tasks Under Stability and Schedulability Constraints. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hawila_et_al:LIPIcs.ECRTS.2025.7,
  author =	{Hawila, Ismail and Cucu-Grosjean, Liliana and Ben Amor, Slim},
  title =	{{Period Assignment for Real-Time Cascade Control Tasks Under Stability and Schedulability Constraints}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{7:1--7: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.7},
  URN =		{urn:nbn:de:0030-drops-235858},
  doi =		{10.4230/LIPIcs.ECRTS.2025.7},
  annote =	{Keywords: Real-time Systems, Cascade Control, Physical Stability, Control Performance}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.13
Faster Classification of Time-Series Input Streams

Authors: Kunal Agrawal, Sanjoy Baruah, Zhishan Guo, Jing Li, Federico Reghenzani, Kecheng Yang, and Jinhao Zhao

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

Abstract
Deep learning–based classifiers are widely used for perception in autonomous Cyber-Physical Systems (CPS’s). However, such classifiers rarely offer guarantees of perfect accuracy while being optimized for efficiency. To support safety-critical perception, ensembles of multiple different classifiers working in concert are typically used. Since CPS’s interact with the physical world continuously, it is not unreasonable to expect dependencies among successive inputs in a stream of sensor data. Prior work introduced a classification technique that leverages these inter-input dependencies to reduce the average time to successful classification using classifier ensembles. In this paper, we propose generalizations to this classification technique, both in the improved generation of classifier cascades and the modeling of temporal dependencies. We demonstrate, through theoretical analysis and numerical evaluation, that our approach achieves further reductions in average classification latency compared to the prior methods.
Cite as

Kunal Agrawal, Sanjoy Baruah, Zhishan Guo, Jing Li, Federico Reghenzani, Kecheng Yang, and Jinhao Zhao. Faster Classification of Time-Series Input Streams. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2025.13,
  author =	{Agrawal, Kunal and Baruah, Sanjoy and Guo, Zhishan and Li, Jing and Reghenzani, Federico and Yang, Kecheng and Zhao, Jinhao},
  title =	{{Faster Classification of Time-Series Input Streams}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{13:1--13:22},
  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.13},
  URN =		{urn:nbn:de:0030-drops-235919},
  doi =		{10.4230/LIPIcs.ECRTS.2025.13},
  annote =	{Keywords: Classification, Deep Learning, Sensor data streams, IDK classifiers}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.15
Analysis of EDF for Real-Time Multiprocessor Systems with Resource Sharing

Authors: Kunal Agrawal, Sanjoy Baruah, Jeremy T. Fineman, Alberto Marchetti-Spaccamela, and Jinhao Zhao

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

Abstract
The classic Earliest Deadline First (EDF) algorithm is widely studied and used due to its simplicity and strong theoretical performance, but has not been rigorously analyzed for systems where jobs may execute critical sections protected by shared locks. Analyzing such systems is often challenging due to unpredictable delays caused by contention. In this paper, we propose a straightforward generalization of EDF, called EDF-Block. In this generalization, the critical sections are executed non-preemptively, but scheduling and lock acquisition priorities are based on EDF. We establish lower bounds on the speed augmentation required for any non-clairvoyant scheduler (EDF-Block is an example of non-clairvoyant schedulers) and for EDF-Block, showing that EDF-Block requires at least 4.11× speed augmentation for jobs and 4× for tasks. We then provide an upper bound analysis, demonstrating that EDF-Block requires speedup of at most 6 to schedule all feasible job and task sets.
Cite as

Kunal Agrawal, Sanjoy Baruah, Jeremy T. Fineman, Alberto Marchetti-Spaccamela, and Jinhao Zhao. Analysis of EDF for Real-Time Multiprocessor Systems with Resource Sharing. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 15:1-15:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2025.15,
  author =	{Agrawal, Kunal and Baruah, Sanjoy and Fineman, Jeremy T. and Marchetti-Spaccamela, Alberto and Zhao, Jinhao},
  title =	{{Analysis of EDF for Real-Time Multiprocessor Systems with Resource Sharing}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{15:1--15:26},
  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.15},
  URN =		{urn:nbn:de:0030-drops-235932},
  doi =		{10.4230/LIPIcs.ECRTS.2025.15},
  annote =	{Keywords: Real-Time Scheduling, Non-Clairvoyant Scheduling, EDF, Competitive Analysis, Shared Resources}
}
Document
Artifact
DOI: 10.4230/DARTS.11.1.4
Faster Classification of Time-Series Input Streams (Artifact)

Authors: Kunal Agrawal, Sanjoy Baruah, Zhishan Guo, Jing Li, Federico Reghenzani, Kecheng Yang, and Jinhao Zhao

Published in: DARTS, Volume 11, Issue 1, Special Issue of the 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)

Abstract
Deep learning–based classifiers are widely used for perception in autonomous Cyber-Physical Systems (CPS’s). However, such classifiers rarely offer guarantees of perfect accuracy while being optimized for efficiency. To support safety-critical perception, ensembles of multiple different classifiers working in concert are typically used. Since CPS’s interact with the physical world continuously, it is not unreasonable to expect dependencies among successive inputs in a stream of sensor data. Prior work introduced a classification technique that leverages these inter-input dependencies to reduce the average time to successful classification using classifier ensembles. In this paper, we propose generalizations to this classification technique, both in the improved generation of classifier cascades and the modeling of temporal dependencies. We demonstrate, through theoretical analysis and numerical evaluation, that our approach achieves further reductions in average classification latency compared to the prior methods.
Cite as

Kunal Agrawal, Sanjoy Baruah, Zhishan Guo, Jing Li, Federico Reghenzani, Kecheng Yang, and Jinhao Zhao. Faster Classification of Time-Series Input Streams (Artifact). In Special Issue of the 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Dagstuhl Artifacts Series (DARTS), Volume 11, Issue 1, pp. 4:1-4:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{agrawal_et_al:DARTS.11.1.4,
  author =	{Agrawal, Kunal and Baruah, Sanjoy and Guo, Zhishan and Li, Jing and Reghenzani, Federico and Yang, Kecheng and Zhao, Jinhao},
  title =	{{Faster Classification of Time-Series Input Streams (Artifact)}},
  pages =	{4:1--4:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2025},
  volume =	{11},
  number =	{1},
  editor =	{Agrawal, Kunal and Baruah, Sanjoy and Guo, Zhishan and Li, Jing and Reghenzani, Federico and Yang, Kecheng and Zhao, Jinhao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.11.1.4},
  URN =		{urn:nbn:de:0030-drops-236057},
  doi =		{10.4230/DARTS.11.1.4},
  annote =	{Keywords: Classification, Deep Learning, Sensor data streams, IDK classifiers}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.14
IsaBIL: A Framework for Verifying (In)correctness of Binaries in Isabelle/HOL

Authors: Matt Griffin, Brijesh Dongol, and Azalea Raad

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
This paper presents IsaBIL, a binary analysis framework in Isabelle/HOL that is based on the widely used Binary Analysis Platform (BAP). Specifically, in IsaBIL, we formalise BAP’s intermediate language, called BIL and integrate it with Hoare logic (to enable proofs of correctness) as well as incorrectness logic (to enable proofs of incorrectness). IsaBIL inherits the full flexibility of BAP, allowing us to verify binaries for a wide range of languages (C, C++, Rust), toolchains (LLVM, Ghidra) and target architectures (x86, RISC-V), and can also be used when the source code for a binary is unavailable. To make verification tractable, we develop a number of big-step rules that combine BIL’s existing small-step rules at different levels of abstraction to support reuse. We develop high-level reasoning rules for RISC-V instructions (our main target architecture) to further optimise verification. Additionally, we develop Isabelle proof tactics that exploit common patterns in C binaries for RISC-V to discharge large numbers of proof goals (often in the 100s) automatically. IsaBIL includes an Isabelle/ML based parser for BIL programs, allowing one to automatically generate the associated Isabelle/HOL program locale from a BAP output. Taken together, IsaBIL provides a highly flexible proof environment for program binaries. As examples, we prove correctness of key examples from the Joint Strike Fighter coding standards and the MITRE database.
Cite as

Matt Griffin, Brijesh Dongol, and Azalea Raad. IsaBIL: A Framework for Verifying (In)correctness of Binaries in Isabelle/HOL. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 14:1-14:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{griffin_et_al:LIPIcs.ECOOP.2025.14,
  author =	{Griffin, Matt and Dongol, Brijesh and Raad, Azalea},
  title =	{{IsaBIL: A Framework for Verifying (In)correctness of Binaries in Isabelle/HOL}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{14:1--14:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.14},
  URN =		{urn:nbn:de:0030-drops-233070},
  doi =		{10.4230/LIPIcs.ECOOP.2025.14},
  annote =	{Keywords: Binary Analysis Platform, Isabelle/HOL, Hoare Logic, Incorrectness Logic}
}
Document
DOI: 10.4230/LITES.10.1.3
Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks

Authors: Benjamin Standaert, Fatima Raadia, Marion Sudvarg, Sanjoy Baruah, Thidapat Chantem, Nathan Fisher, and Christopher Gill

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

Abstract
Safety-critical embedded systems such as autonomous vehicles typically have only very limited computational capabilities on board that must be carefully managed to provide required enhanced functionalities. As these systems become more complex and inter-connected, some parts may need to be secured to prevent unauthorized access, or isolated to ensure correctness. We propose the multi-phase secure (MPS) task model as a natural extension of the widely used sporadic task model for modeling both the timing and the security (and isolation) requirements for such systems. Under MPS, task phases reflect execution using different security mechanisms which each have associated execution time costs for startup and teardown. We develop corresponding limited-preemption EDF scheduling algorithms and associated pseudo-polynomial schedulability tests for constrained-deadline MPS tasks. In doing so, we provide a correction to a long-standing schedulability condition for EDF under limited-preemption. Evaluation shows that the proposed tests are efficient to compute for bounded utilizations. We empirically demonstrate that the MPS model successfully schedules more task sets compared to non-preemptive approaches.
Cite as

Benjamin Standaert, Fatima Raadia, Marion Sudvarg, Sanjoy Baruah, Thidapat Chantem, Nathan Fisher, and Christopher Gill. Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks. In LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1, pp. 3:1-3:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{standaert_et_al:LITES.10.1.3,
  author =	{Standaert, Benjamin and Raadia, Fatima and Sudvarg, Marion and Baruah, Sanjoy and Chantem, Thidapat and Fisher, Nathan and Gill, Christopher},
  title =	{{Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{3:1--3:27},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.1.3},
  URN =		{urn:nbn:de:0030-drops-230799},
  doi =		{10.4230/LITES.10.1.3},
  annote =	{Keywords: real-time systems, limited-preemption scheduling, trusted execution environments}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2023.2
Towards Efficient Explainability of Schedulability Properties in Real-Time Systems

Authors: Sanjoy Baruah and Pontus Ekberg

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
The notion of efficient explainability was recently introduced in the context of hard-real-time scheduling: a claim that a real-time system is schedulable (i.e., that it will always meet all deadlines during run-time) is defined to be efficiently explainable if there is a proof of such schedulability that can be verified by a polynomial-time algorithm. We further explore this notion by (i) classifying a variety of common schedulability analysis problems according to whether they are efficiently explainable or not; and (ii) developing strategies for dealing with those determined to not be efficiently schedulable, primarily by identifying practically meaningful sub-problems that are efficiently explainable.
Cite as

Sanjoy Baruah and Pontus Ekberg. Towards Efficient Explainability of Schedulability Properties in Real-Time Systems. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baruah_et_al:LIPIcs.ECRTS.2023.2,
  author =	{Baruah, Sanjoy and Ekberg, Pontus},
  title =	{{Towards Efficient Explainability of Schedulability Properties in Real-Time Systems}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.2},
  URN =		{urn:nbn:de:0030-drops-180313},
  doi =		{10.4230/LIPIcs.ECRTS.2023.2},
  annote =	{Keywords: Recurrent Task Systems, Uniprocessor and Multiprocessor Schedulability, Verification, Explanation, Computational Complexity, Approximation Schemes}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2023.3
The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems

Authors: Kunal Agrawal, Sanjoy Baruah, Michael A. Bender, and Alberto Marchetti-Spaccamela

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
The algorithm-design paradigm of algorithms using predictions is explored as a means of incorporating the computations of lower-assurance components (such as machine-learning based ones) into safety-critical systems that must have their correctness validated to very high levels of assurance. The paradigm is applied to two simple example applications that are relevant to the real-time systems community: energy-aware scheduling, and classification using ML-based classifiers in conjunction with more reliable but slower deterministic classifiers. It is shown how algorithms using predictions achieve much-improved performance when the low-assurance computations are correct, at a cost of no more than a slight performance degradation even when they turn out to be completely wrong.
Cite as

Kunal Agrawal, Sanjoy Baruah, Michael A. Bender, and Alberto Marchetti-Spaccamela. The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2023.3,
  author =	{Agrawal, Kunal and Baruah, Sanjoy and Bender, Michael A. and Marchetti-Spaccamela, Alberto},
  title =	{{The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.3},
  URN =		{urn:nbn:de:0030-drops-180323},
  doi =		{10.4230/LIPIcs.ECRTS.2023.3},
  annote =	{Keywords: Algorithms using predictions, robust scheduling, energy minimization, classification, on-line scheduling}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2022.14
An Approach to Formally Specifying the Behaviour of Mixed-Criticality Systems

Authors: A. Burns and Cliff B. Jones

Published in: LIPIcs, Volume 231, 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
This paper proposes a formal framework for describing the relationship between a criticality-aware scheduler and a set of application tasks that are assigned different criticality levels. The exposition employs a series of examples starting with scheduling simple jobs and then moving on to mixed-criticality robust and resilient tasks. The proposed formalism extends the rely-guarantee approach, which facilitates formal reasoning about the functional behaviour of concurrent systems, to address real-time properties.
Cite as

A. Burns and Cliff B. Jones. An Approach to Formally Specifying the Behaviour of Mixed-Criticality Systems. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{burns_et_al:LIPIcs.ECRTS.2022.14,
  author =	{Burns, A. and Jones, Cliff B.},
  title =	{{An Approach to Formally Specifying the Behaviour of Mixed-Criticality Systems}},
  booktitle =	{34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
  pages =	{14:1--14:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-239-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{231},
  editor =	{Maggio, Martina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.14},
  URN =		{urn:nbn:de:0030-drops-163315},
  doi =		{10.4230/LIPIcs.ECRTS.2022.14},
  annote =	{Keywords: real-time, scheduling, mixed criticality, rely/guaranteed conditions}
}
  • Refine by Type
  • 51 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 12 2025
  • 2 2023
  • 1 2022
  • 2 2021
  • 1 2020
  • Show More...

  • Refine by Author
  • 17 Baruah, Sanjoy
  • 8 Agrawal, Kunal
  • 6 Baruah, Sanjoy K.
  • 4 Bini, Enrico
  • 4 Cucu-Grosjean, Liliana
  • Show More...

  • Refine by Series/Journal
  • 18 LIPIcs
  • 2 DARTS
  • 15 LITES
  • 2 DagRep
  • 14 DagSemProc

  • Refine by Classification
  • 20 Computer systems organization → Real-time systems
  • 11 Software and its engineering → Real-time schedulability
  • 9 Computer systems organization → Embedded and cyber-physical systems
  • 4 Software and its engineering → Scheduling
  • 2 Computer systems organization → Embedded software
  • Show More...

  • Refine by Keyword
  • 10 Scheduling
  • 4 Real-Time Systems
  • 4 mixed criticality
  • 4 real-time
  • 3 Real-time systems
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact