DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2024.7

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy

Authors: Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

The following question arises naturally in the study of graph streaming algorithms: Is there any graph problem which is "not too hard", in that it can be solved efficiently with total communication (nearly) linear in the number n of vertices, and for which, nonetheless, any streaming algorithm with Õ(n) space (i.e., a semi-streaming algorithm) needs a polynomial n^Ω(1) number of passes? Assadi, Chen, and Khanna [STOC 2019] were the first to prove that this is indeed the case. However, the lower bounds that they obtained are for rather non-standard graph problems. Our first main contribution is to present the first polynomial-pass lower bounds for natural "not too hard" graph problems studied previously in the streaming model: k-cores and degeneracy. We devise a novel communication protocol for both problems with near-linear communication, thus showing that k-cores and degeneracy are natural examples of "not too hard" problems. Indeed, previous work have developed single-pass semi-streaming algorithms for approximating these problems. In contrast, we prove that any semi-streaming algorithm for exactly solving these problems requires (almost) Ω(n^{1/3}) passes. The lower bound follows by a reduction from a generalization of the hidden pointer chasing (HPC) problem of Assadi, Chen, and Khanna, which is also the basis of their earlier semi-streaming lower bounds. Our second main contribution is improved round-communication lower bounds for the underlying communication problems at the basis of these reductions: - We improve the previous lower bound of Assadi, Chen, and Khanna for HPC to achieve optimal bounds for this problem. - We further observe that all current reductions from HPC can also work with a generalized version of this problem that we call MultiHPC, and prove an even stronger and optimal lower bound for this generalization. These two results collectively allow us to improve the resulting pass lower bounds for semi-streaming algorithms by a polynomial factor, namely, from n^{1/5} to n^{1/3} passes.

Cite as

Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7,
  author =	{Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik},
  title =	{{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.7},
  URN =		{urn:nbn:de:0030-drops-204035},
  doi =		{10.4230/LIPIcs.CCC.2024.7},
  annote =	{Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy}
}

Document

DOI: 10.4230/LIPIcs.ECRTS.2024.8

Deadline Miss Early Detection Method for DAG Tasks Considering Variable Execution Time

Authors: Hayate Toba and Takuya Azumi

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract

Autonomous driving systems must guarantee safety, which requires strict real-time performance. A series of processes, from sensor data input to vehicle control command output, must be completed by the end-to-end deadline. If a deadline miss occurs, the system must quickly transition to a safe state. To improve safety, an early detection method for deadline misses was proposed. The proposed method represents the autonomous driving system as a directed acyclic graph (DAG) with a mixture of timer-driven and event-driven nodes. It assigns appropriate time constraints for each node based on the end-to-end deadline. However, the existing methods assume the worst-case execution time (WCET) for calculating the time constraints of each node and do not consider the execution time variation of nodes, making the detection of deadline misses pessimistic. This paper proposes a deadline miss early detection method to determine the possibility of deadline misses quantitatively at the beginning of each node execution in a DAG task. It calculates the time constraints of each node using probabilistic execution time, which treats execution time as a random variable. Experimental evaluation shows that the proposed method reduces pessimism, which is a problem of conventional methods using WCET, and then achieves more accurate early detection of deadline misses. The evaluation also indicates that the execution time of static analysis required for deadline miss early detection is within a practical level.

Cite as

Hayate Toba and Takuya Azumi. Deadline Miss Early Detection Method for DAG Tasks Considering Variable Execution Time. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{toba_et_al:LIPIcs.ECRTS.2024.8,
  author =	{Toba, Hayate and Azumi, Takuya},
  title =	{{Deadline Miss Early Detection Method for DAG Tasks Considering Variable Execution Time}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.8},
  URN =		{urn:nbn:de:0030-drops-203116},
  doi =		{10.4230/LIPIcs.ECRTS.2024.8},
  annote =	{Keywords: Autonomous driving system, deadline miss early detection, DAG, event-driven task, timer-driven task, probabilistic execution time}
}

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.FUN.2021.7

1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Authors: Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract

Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.

Cite as

Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7,
  author =	{Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi},
  title =	{{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7},
  URN =		{urn:nbn:de:0030-drops-127681},
  doi =		{10.4230/LIPIcs.FUN.2021.7},
  annote =	{Keywords: puzzles, sliding blocks, PSPACE-hardness}
}

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/DagRep.9.3.1

Analysis, Design, and Control of Predictable Interconnected Systems (Dagstuhl Seminar 19101)

Authors: Kunal Agrawal, Enrico Bini, and Giovanni Stea

Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)

Abstract

We call "Interconnected Systems" any collection of systems distributed over a metric space whose behavior is influenced by its neighborhood. Examples of interconnected systems exist at very different scales: different cores over the same silicon, different sub-systems in vehicles, communicating nodes over either a physical (e.g., optical) network, or - more recently - virtualized network. Examples also exist in contexts which are not related to computing or communication. Smart Grids (of energy production, distribution, and consumption) and Intelligent Transportation Systems are just two notable examples. The common characteristic among all these examples is the presence of a spatially distributed demand of resources (energy, computing, communication bandwidth, etc.) which needs to be matched with a spatially distributed supply. Often times demands and availability of resources of different types (e.g., computing and link bandwidth in virtualized network environments) need to be matched simultaneously. Time predictability is a key requirement for above systems. Despite this, the strong market pressure has often led to ``quick and dirty'' best-effort solutions, which make it extremely challenging to predict the behavior of such systems. Research communities have developed formal theories for predictability which are specialized to each application domain or type of resource (e.g., schedulability analysis for real-time systems or network calculus for communication systems). However, the emerging application domains (virtualized networks, cyber-physical systems, etc.) clearly require a unified, holistic approach. By leveraging the expertise, vision and interactions of scientists that have addressed predictability in different areas, the proposed seminar aims at constructing a common ground for the theory supporting the analysis, the design, and the control of predictable interconnected systems.

Cite as

Kunal Agrawal, Enrico Bini, and Giovanni Stea. Analysis, Design, and Control of Predictable Interconnected Systems (Dagstuhl Seminar 19101). In Dagstuhl Reports, Volume 9, Issue 3, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.9.3.1,
  author =	{Agrawal, Kunal and Bini, Enrico and Stea, Giovanni},
  title =	{{Analysis, Design, and Control of Predictable Interconnected Systems (Dagstuhl Seminar 19101)}},
  pages =	{1--15},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{3},
  editor =	{Agrawal, Kunal and Bini, Enrico and Stea, Giovanni},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.1},
  URN =		{urn:nbn:de:0030-drops-112882},
  doi =		{10.4230/DagRep.9.3.1},
  annote =	{Keywords: distributed resource management, network calculus, real-time systems}
}

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},
  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}
}

9 Search Results for "Agrawal, Kunal"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as