Search Results

Documents authored by Baruah, Sanjoy K.

Found 2 Possible Name Variants:

Baruah, Sanjoy K.

Document
DOI: 10.4230/DagRep.7.3.70
Mixed Criticality on Multicore / Manycore Platforms (Dagstuhl Seminar 17131)

Authors: Liliana Cucu-Grosjean, Robert Davis, Sanjoy K. Baruah, and Zoë Stephenson

Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)

Abstract
This report provides an overview of the discussions, the program and the outcomes of the second Dagstuhl Seminar on Mixed Criticality on Multicore/Manycore Platforms. The seminar brought together researchers working on mixed criticality real-time applications, industrialists from the aerospace, railway, and automotive industries, and experts in certification.
Cite as

Liliana Cucu-Grosjean, Robert Davis, Sanjoy K. Baruah, and Zoë Stephenson. Mixed Criticality on Multicore / Manycore Platforms (Dagstuhl Seminar 17131). In Dagstuhl Reports, Volume 7, Issue 3, pp. 70-98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{cucugrosjean_et_al:DagRep.7.3.70,
  author =	{Cucu-Grosjean, Liliana and Davis, Robert and Baruah, Sanjoy K. and Stephenson, Zo\"{e}},
  title =	{{Mixed Criticality on Multicore / Manycore Platforms (Dagstuhl Seminar 17131)}},
  pages =	{70--98},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{3},
  editor =	{Cucu-Grosjean, Liliana and Davis, Robert and Baruah, Sanjoy K. and Stephenson, Zo\"{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.3.70},
  URN =		{urn:nbn:de:0030-drops-73622},
  doi =		{10.4230/DagRep.7.3.70},
  annote =	{Keywords: mixed-criticality multicore manycore real-time-systems}
}
Document
DOI: 10.4230/DagRep.5.3.84
Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 15121)

Authors: Sanjoy K. Baruah, Liliana Cucu-Grosjean, Roabert I. Davis, and Claire Maiza

Published in: Dagstuhl Reports, Volume 5, Issue 3 (2015)

Abstract
This report provides an overview of the discussions, the program and the outcomes of the first Dagstuhl Seminar on Mixed Criticality on multicore/Manycore Platforms. The seminar brought together researchers working on challenges related to executing mixed criticality real-time applications on multicore and manycore architectures with the main purpose of promoting a closer interaction between the sub-communities involved in real-time scheduling, real-time operating systems / runtime environments, and timing analysis as well as interaction with specialists in hardware architectures.
Cite as

Sanjoy K. Baruah, Liliana Cucu-Grosjean, Roabert I. Davis, and Claire Maiza. Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 15121). In Dagstuhl Reports, Volume 5, Issue 3, pp. 84-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{baruah_et_al:DagRep.5.3.84,
  author =	{Baruah, Sanjoy K. and Cucu-Grosjean, Liliana and Davis, Roabert I. and Maiza, Claire},
  title =	{{Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 15121)}},
  pages =	{84--142},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{3},
  editor =	{Baruah, Sanjoy K. and Cucu-Grosjean, Liliana and Davis, Roabert I. and Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.3.84},
  URN =		{urn:nbn:de:0030-drops-52707},
  doi =		{10.4230/DagRep.5.3.84},
  annote =	{Keywords: Mixed-Criticality, Real-time systems, Multicore/Manycore Platforms, fixed priority; probabilistic scheduling, varying-speed processors model combination}
}
Document
DOI: 10.4230/LITES-v001-i002-a003
Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor

Authors: Zhishan Guo and Sanjoy K. Baruah

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

Abstract
A mixed criticality (MC) workload consists of components of varying degrees of importance (or "criticalities"); the more critical components typically need to have their correctness validated to greater levels of assurance than the less critical ones. The problem of executing such a MC workload upon a preemptive processor whose effective speed may vary during run-time, in a manner that is not completely known prior to run-time, is considered.Such a processor is modeled as being characterized by several execution speeds: a normal speed and several levels of degraded speed. Under normal circumstances it will execute at or above its normal speed; conditions during run-time may cause it to execute slower. It is desired that all components of the MC workload execute correctly under normal circumstances. If the processor speed degrades, it should nevertheless remain the case that the more critical components execute correctly (although the less critical ones need not do so).In this work, we derive an optimal algorithm for scheduling MC workloads upon such platforms; achieving optimality does not require that the processor be able to monitor its own run-time speed. For the sub-case of the general problem where there are only two criticality levels defined, we additionally provide an implementation that is asymptotically optimal in terms of run-time efficiency.
Cite as

Zhishan Guo and Sanjoy K. Baruah. Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor. In LITES, Volume 1, Issue 2 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 2, pp. 03:1-03:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{guo_et_al:LITES-v001-i002-a003,
  author =	{Guo, Zhishan and Baruah, Sanjoy K.},
  title =	{{Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{03:1--03:19},
  ISSN =	{2199-2002},
  year =	{2014},
  volume =	{1},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v001-i002-a003},
  URN =		{urn:nbn:de:0030-drops-192498},
  doi =		{10.4230/LITES-v001-i002-a003},
  annote =	{Keywords: Mixed criticalities, Varying-speed processor, Preemptive uniprocessor scheduling, }
}
Document
DOI: 10.4230/DagSemProc.10071.1
10071 Abstracts Collection – Scheduling

Authors: Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
From 14.02. to 19.02.2010, the Dagstuhl Seminar 10071 ``Scheduling '' was held in Schloss Dagstuhl-Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs. 10071 Abstracts Collection – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.10071.1,
  author =	{Albers, Susanne and Baruah, Sanjoy K. and M\"{o}hring, Rolf  H. and Pruhs, Kirk},
  title =	{{10071 Abstracts Collection – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.1},
  URN =		{urn:nbn:de:0030-drops-25479},
  doi =		{10.4230/DagSemProc.10071.1},
  annote =	{Keywords: Scheduling, real-time, complexity, approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.10071.2
10071 Executive Summary – Scheduling

Authors: Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
The primary objectives of this seminar were to bring together leading researchers working on scheduling problems in three different research communities – operations research, theoretical computer science, and real-time systems – to expose each community to the important problems addressed by the other communities; to enable and encourage cooperation among the researchers; and to facilitate a transfer of solution techniques from each community to the others.
Cite as

Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs. 10071 Executive Summary – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.10071.2,
  author =	{Albers, Susanne and Baruah, Sanjoy K. and M\"{o}hring, Rolf  H. and Pruhs, Kirk},
  title =	{{10071 Executive Summary – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.2},
  URN =		{urn:nbn:de:0030-drops-25417},
  doi =		{10.4230/DagSemProc.10071.2},
  annote =	{Keywords: Scheduling, real-time, complexity, approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.10071.14
The Parallel Supply Function Abstraction for a Virtual Multiprocessor

Authors: Enrico Bini, Bertogna Marko, and Sanjoy K. Baruah

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
A new abstraction --- the Parallel Supply Function (PSF) --- is proposed for representing the computing capabilities offered by virtual platforms implemented atop identical multiprocessors. It is shown that this abstraction is strictly more powerful than previously-proposed ones, from the perspective of more accurately representing the inherent parallelism of the provided computing capabilities. Sufficient tests are derived for determining whether a given real-time task system, represented as a collection of sporadic tasks, is guaranteed to always meet all deadlines when scheduled upon a specified virtual platform using the global EDF scheduling algorithm.
Cite as

Enrico Bini, Bertogna Marko, and Sanjoy K. Baruah. The Parallel Supply Function Abstraction for a Virtual Multiprocessor. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.10071.14,
  author =	{Bini, Enrico and Marko, Bertogna and Baruah, Sanjoy K.},
  title =	{{The Parallel Supply Function Abstraction for a Virtual Multiprocessor}},
  booktitle =	{Scheduling},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.14},
  URN =		{urn:nbn:de:0030-drops-25423},
  doi =		{10.4230/DagSemProc.10071.14},
  annote =	{Keywords: Virtual multiprocessor}
}

Baruah, Sanjoy

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/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.2021.9
Graceful Degradation in Semi-Clairvoyant Scheduling

Authors: Sanjoy Baruah and Pontus Ekberg

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

Abstract
In the Vestal model of mixed-criticality systems, jobs are characterized by multiple different estimates of their actual, but unknown, worst-case execution time (WCET) parameters. Some recent research has focused upon a semi-clairvoyant model for mixed-criticality systems in which it is assumed that each job reveals upon arrival which of its WCET parameters it will respect. We study the problem of scheduling such semi-clairvoyant systems to ensure graceful degradation of service to less critical jobs in the event that the systems exhibit high-criticality behavior. We propose multiple different interpretations of graceful degradation in such systems, and derive efficient scheduling algorithms that are capable of ensuring graceful degradation under these different interpretations.
Cite as

Sanjoy Baruah and Pontus Ekberg. Graceful Degradation in Semi-Clairvoyant Scheduling. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{baruah_et_al:LIPIcs.ECRTS.2021.9,
  author =	{Baruah, Sanjoy and Ekberg, Pontus},
  title =	{{Graceful Degradation in Semi-Clairvoyant Scheduling}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.9},
  URN =		{urn:nbn:de:0030-drops-139404},
  doi =		{10.4230/LIPIcs.ECRTS.2021.9},
  annote =	{Keywords: Mixed criticality, semi-clairvoyance, graceful degradation}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2021.12
Feasibility Analysis of Conditional DAG Tasks

Authors: Sanjoy Baruah and Alberto Marchetti-Spaccamela

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

Abstract
Feasibility analysis for Conditional DAG tasks (C-DAGs) upon multiprocessor platforms is shown to be complete for the complexity class pspace. It is shown that as a consequence integer linear programming solvers (ILP solvers) are likely to prove inadequate for such analysis. A demarcation is identified between the feasibility-analysis problems on C-DAGs that are efficiently solvable using ILP solvers and those that are not, by characterizing a restricted class of C-DAGs for which feasibility analysis is shown to be efficiently solvable using ILP solvers.
Cite as

Sanjoy Baruah and Alberto Marchetti-Spaccamela. Feasibility Analysis of Conditional DAG Tasks. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{baruah_et_al:LIPIcs.ECRTS.2021.12,
  author =	{Baruah, Sanjoy and Marchetti-Spaccamela, Alberto},
  title =	{{Feasibility Analysis of Conditional DAG Tasks}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.12},
  URN =		{urn:nbn:de:0030-drops-139433},
  doi =		{10.4230/LIPIcs.ECRTS.2021.12},
  annote =	{Keywords: Multiprocessor feasibility analysis, Conditional Directed Acyclic Graphs, PSPACE-complete}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2020.7
The Safe and Effective Use of Learning-Enabled Components in Safety-Critical Systems

Authors: Kunal Agrawal, Sanjoy Baruah, and Alan Burns

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract
Autonomous systems increasingly use components that incorporate machine learning and other AI-based techniques in order to achieve improved performance. The problem of assuring correctness in safety-critical systems that use such components is considered. A model is proposed in which components are characterized according to both their worst-case and their typical behaviors; it is argued that while safety must be assured under all circumstances, it is reasonable to be concerned with providing a high degree of performance for typical behaviors only. The problem of assuring safety while providing such improved performance is formulated as an optimization problem in which performance under typical circumstances is the objective function to be optimized while safety is a hard constraint that must be satisfied. Algorithmic techniques are applied to derive an optimal solution to this optimization problem. This optimal solution is compared with an alternative approach that optimizes for performance under worst-case conditions, as well as some common-sense heuristics, via simulation experiments on synthetically-generated workloads.
Cite as

Kunal Agrawal, Sanjoy Baruah, and Alan Burns. The Safe and Effective Use of Learning-Enabled Components in Safety-Critical Systems. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2020.7,
  author =	{Agrawal, Kunal and Baruah, Sanjoy and Burns, Alan},
  title =	{{The Safe and Effective Use of Learning-Enabled Components in Safety-Critical Systems}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.7},
  URN =		{urn:nbn:de:0030-drops-123704},
  doi =		{10.4230/LIPIcs.ECRTS.2020.7},
  annote =	{Keywords: Learning-enabled components (LECs), Safety-critical systems, Typical analysis, Performance optimization, Run-time monitoring}
}
Document
DOI: 10.4230/LITES-v006-i001-a005
Elastic Scheduling for Parallel Real-Time Systems

Authors: James Orr, Chris Gill, Kunal Agrawal, Jing Li, and Sanjoy Baruah

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

Abstract
The elastic task model was introduced by Buttazzo et al.~in order to represent recurrent real-time workloads executing upon uniprocessor platforms that are somewhat flexible with regards to timing constraints.  In this work, we propose an extension of this model and apply it to represent recurrent real-time workloads that exhibit internal parallelism and are executed on multiprocessor platforms. In our proposed extension, the elasticity coefficient - the quantitative measure of a task's elasticity that was introduced in the model proposed by Buttazzo et al. - is interpreted in the same manner as in the original (sequential) model. Hence, system developers who are familiar with the elastic task model in the uniprocessor context may use our more general model as they had previously done, now for real-time tasks whose computational demands require them to utilize more than one processor.
Cite as

James Orr, Chris Gill, Kunal Agrawal, Jing Li, and Sanjoy Baruah. Elastic Scheduling for Parallel Real-Time Systems. In LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1, pp. 05:1-05:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{orr_et_al:LITES-v006-i001-a005,
  author =	{Orr, James and Gill, Chris and Agrawal, Kunal and Li, Jing and Baruah, Sanjoy},
  title =	{{Elastic Scheduling for Parallel Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{05:1--05:14},
  ISSN =	{2199-2002},
  year =	{2019},
  volume =	{6},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v006-i001-a005},
  URN =		{urn:nbn:de:0030-drops-192819},
  doi =		{10.4230/LITES-v006-i001-a005},
  annote =	{Keywords: Parallel real-time tasks, multiprocessor federated scheduling, elasticity coefficient}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2018.5
A Measurement-Based Model for Parallel Real-Time Tasks

Authors: Kunal Agrawal and Sanjoy Baruah

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
Under the federated paradigm of multiprocessor scheduling, a set of processors is reserved for the exclusive use of each real-time task. If tasks are characterized very conservatively (as is typical in safety-critical systems), it is likely that most invocations of the task will have computational demand far below the worst-case characterization, and could have been scheduled correctly upon far fewer processors than were assigned to it assuming the worst-case characterization of its run-time behavior. Provided we could safely determine during run-time when all the processors are going to be needed, for the rest of the time the unneeded processors could be idled in low-energy "sleep" mode, or used for executing non-real time work in the background. In this paper we propose a model for representing parallelizable real-time tasks in a manner that permits us to do so. Our model does not require us to have fine-grained knowledge of the internal structure of the code represented by the task; rather, it characterizes each task by a few parameters that are obtained by repeatedly executing the code under different conditions and measuring the run-times.
Cite as

Kunal Agrawal and Sanjoy Baruah. A Measurement-Based Model for Parallel Real-Time Tasks. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2018.5,
  author =	{Agrawal, Kunal and Baruah, Sanjoy},
  title =	{{A Measurement-Based Model for Parallel Real-Time Tasks}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.5},
  URN =		{urn:nbn:de:0030-drops-89999},
  doi =		{10.4230/LIPIcs.ECRTS.2018.5},
  annote =	{Keywords: multiprocessor federated scheduling, parallel tasks, work and span, mixed criticality}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2018.11
Intractability Issues in Mixed-Criticality Scheduling

Authors: Kunal Agrawal and Sanjoy Baruah

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
In seeking to develop mixed-criticality scheduling algorithms, one encounters challenges arising from two sources. First, mixed-criticality scheduling is an inherently an on-line problem in that scheduling decisions must be made without access to all the information that is needed to make such decisions optimally - such information is only revealed over time. Second, many fundamental mixed-criticality schedulability analysis problems are computationally intractable - NP-hard in the strong sense - but we desire to solve these problems using algorithms with polynomial or pseudo-polynomial running time. While these two aspects of intractability are traditionally studied separately in the theoretical computer science literature, they have been considered in an integrated fashion in mixed-criticality scheduling theory. In this work we seek to separate out the effects of being inherently on-line, and being computationally intractable, on the overall intractability of mixed-criticality scheduling problems. Speedup factor is widely used as quantitative metric of the effectiveness of mixed-criticality scheduling algorithms; there has recently been a bit of a debate regarding the appropriateness of doing so. We provide here some additional perspective on this matter: we seek to better understand its appropriateness as well as its limitations in this regard by examining separately how the on-line nature of some mixed-criticality problems, and their computational complexity, contribute to the speedup factors of two widely-studied mixed-criticality scheduling algorithms.
Cite as

Kunal Agrawal and Sanjoy Baruah. Intractability Issues in Mixed-Criticality Scheduling. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2018.11,
  author =	{Agrawal, Kunal and Baruah, Sanjoy},
  title =	{{Intractability Issues in Mixed-Criticality Scheduling}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.11},
  URN =		{urn:nbn:de:0030-drops-89925},
  doi =		{10.4230/LIPIcs.ECRTS.2018.11},
  annote =	{Keywords: mixed-criticality scheduling, speedup factor, competitive ratio, approximation ratio, NP-completeness results, sporadic tasks}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2018.14
AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems

Authors: Alessandro Vittorio Papadopoulos, Enrico Bini, Sanjoy Baruah, and Alan Burns

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
A system is said to be resilient if slight deviations from expected behavior during run-time does not lead to catastrophic degradation of performance: minor deviations should result in no more than minor performance degradation. In mixed-criticality systems, such degradation should additionally be criticality-cognizant. The applicability of control theory is explored for the design of resilient run-time scheduling algorithms for mixed-criticality systems. Recent results in control theory have shown how appropriately designed controllers can provide guaranteed service to hard-real-time servers; this prior work is extended to allow for such guarantees to be made concurrently to multiple criticality-cognizant servers. The applicability of this approach is explored via several experimental simulations in a dual-criticality setting. These experiments demonstrate that our control-based run-time schedulers can be synthesized in such a manner that bounded deviations from expected behavior result in the high-criticality server suffering no performance degradation and the lower-criticality one, bounded performance degradation.
Cite as

Alessandro Vittorio Papadopoulos, Enrico Bini, Sanjoy Baruah, and Alan Burns. AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{papadopoulos_et_al:LIPIcs.ECRTS.2018.14,
  author =	{Papadopoulos, Alessandro Vittorio and Bini, Enrico and Baruah, Sanjoy and Burns, Alan},
  title =	{{AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.14},
  URN =		{urn:nbn:de:0030-drops-89899},
  doi =		{10.4230/LIPIcs.ECRTS.2018.14},
  annote =	{Keywords: mixed criticality, control theory, run-time resilience, bounded overloads}
}
Document
DOI: 10.4230/DARTS.4.2.1
AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems (Artifact)

Authors: Alessandro Vittorio Papadopoulos, Enrico Bini, Sanjoy Baruah, and Alan Burns

Published in: DARTS, Volume 4, Issue 2, Special Issue of the 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
A system is said to be resilient if slight deviations from expected behavior during run-time does not lead to catastrophic degradation of performance: minor deviations should result in no more than minor performance degradation. In mixed-criticality systems, such degradation should additionally be criticality-cognizant. The applicability of control theory is explored for the design of resilient run-time scheduling algorithms for mixed-criticality systems. Recent results in control theory have shown how appropriately designed controllers can provide guaranteed service to hard-real-time servers; this prior work is extended to allow for such guarantees to be made concurrently to multiple criticality-cognizant servers. The applicability of this approach is explored via several experimental simulations in a dual-criticality setting. These experiments demonstrate that our control-based run-time schedulers can be synthesized in such a manner that bounded deviations from expected behavior result in the high-criticality server suffering no performance degradation and the lower-criticality one, bounded performance degradation.
Cite as

Alessandro Vittorio Papadopoulos, Enrico Bini, Sanjoy Baruah, and Alan Burns. AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems (Artifact). In Special Issue of the 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Dagstuhl Artifacts Series (DARTS), Volume 4, Issue 2, pp. 1:1-1:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{papadopoulos_et_al:DARTS.4.2.1,
  author =	{Papadopoulos, Alessandro Vittorio and Bini, Enrico and Baruah, Sanjoy and Burns, Alan},
  title =	{{AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems (Artifact)}},
  pages =	{1:1--1:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2018},
  volume =	{4},
  number =	{2},
  editor =	{Papadopoulos, Alessandro Vittorio and Bini, Enrico and Baruah, Sanjoy and Burns, Alan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.4.2.1},
  URN =		{urn:nbn:de:0030-drops-89691},
  doi =		{10.4230/DARTS.4.2.1},
  annote =	{Keywords: mixed criticality, control theory, run-time resilience, bounded overloads}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2017.8
Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation

Authors: Abhishek Singh, Pontus Ekberg, and Sanjoy Baruah

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

Abstract
Schedulability analysis techniques that are well understood within the real-time scheduling community are applied to the analysis of recurrent real-time workloads that are modeled using the synchronous data-flow graph (SDFG) model. An enhancement to the standard SDFG model is proposed, that permits the specification of a real-time latency constraint between a specified input and a specified output of an SDFG. A technique is derived for transforming such an enhanced SDFG to a collection of traditional 3-parameter sporadic tasks, thereby allowing for the analysis of systems of SDFG tasks using the methods and algorithms that have previously been developed within the real-time scheduling community for the analysis of systems of such sporadic tasks. The applicability of this approach is illustrated by applying prior results from real-time scheduling theory to construct an exact preemptive uniprocessor schedulability test for collections of recurrent processes that are each represented using the enhanced SDFG model.
Cite as

Abhishek Singh, Pontus Ekberg, and Sanjoy Baruah. Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{singh_et_al:LIPIcs.ECRTS.2017.8,
  author =	{Singh, Abhishek and Ekberg, Pontus and Baruah, Sanjoy},
  title =	{{Applying Real-Time Scheduling Theory to the Synchronous Data Flow Model of Computation}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{8:1--8:22},
  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.8},
  URN =		{urn:nbn:de:0030-drops-71517},
  doi =		{10.4230/LIPIcs.ECRTS.2017.8},
  annote =	{Keywords: Real-Time Systems, Synchronous Dataflow (SDF), Hard Real-Time Streaming Dataflow Applications, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.7
Mixed-Criticality Scheduling to Minimize Makespan

Authors: Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
In the mixed-criticality job model, each job is characterized by two execution time parameters, representing a smaller (less conservative) estimate and a larger (more conservative) estimate on its actual, unknown, execution time. Each job is further classified as being either less critical or more critical. The desired execution semantics are that all jobs should execute correctly provided all jobs complete upon being allowed to execute for up to the smaller of their execution time estimates, whereas if some jobs need to execute beyond their smaller execution time estimates (but not beyond their larger execution time estimates), then only the jobs classified as being more critical are required to execute correctly. The scheduling of collections of such mixed-criticality jobs upon identical multiprocessor platforms in order to minimize the makespan is considered here.
Cite as

Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo. Mixed-Criticality Scheduling to Minimize Makespan. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{baruah_et_al:LIPIcs.FSTTCS.2016.7,
  author =	{Baruah, Sanjoy and Easwaran, Arvind and Guo, Zhishan},
  title =	{{Mixed-Criticality Scheduling to Minimize Makespan}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.7},
  URN =		{urn:nbn:de:0030-drops-68429},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.7},
  annote =	{Keywords: Scheduling, Mixed criticality, Identical parallel machines, Makespan minimization, Approximation algorithm.}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact