35 Search Results for "Ernst, Rolf"

Volume

OASIcs, Volume 68

Workshop on Autonomous Systems Design (ASD 2019)

ASD 2019, March 29, 2019, Florence, Italy

Editors: Selma Saidi, Rolf Ernst, and Dirk Ziegenbein

Document
DOI: 10.4230/LITES.11.1.1
A Survey of Real-Time Support, Analysis, and Advancements in ROS 2

Authors: Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper

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

Abstract
The Robot Operating System 2 (ROS 2) has emerged as a relevant middleware framework for robotic applications, offering modularity, distributed execution, and communication. In the last six years, ROS 2 has drawn increasing attention from the real-time systems community and industry. This survey presents a comprehensive overview of research efforts that analyze, enhance, and extend ROS 2 to support real-time execution. We first provide a detailed description of the internal scheduling mechanisms of ROS 2 and its layered architecture, including the interaction with DDS-based communication and other communication middleware. We then review key contributions from the literature, covering timing analysis for both single- and multi-threaded executors, metrics such as response time, reaction time, and data age, and different communication modes. The survey also discusses community-driven enhancements to the ROS 2 runtime, including new executor algorithm designs, real-time GPU management, and microcontroller support via micro-ROS. Furthermore, we summarize techniques for bounding DDS communication delays, message filters, and profiling tools that have been developed to support analysis and experimentation. To help systematize this growing body of work, we introduce taxonomies that classify the surveyed contributions based on different criteria. This survey aims to guide both researchers and practitioners in understanding and improving the real-time capabilities of ROS 2.
Cite as

Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper. A Survey of Real-Time Support, Analysis, and Advancements in ROS 2. In LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1, pp. 1:1-1:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{casini_et_al:LITES.11.1.1,
  author =	{Casini, Daniel and Chen, Jian-Jia and Li, Jing and Reghenzani, Federico and Teper, Harun},
  title =	{{A Survey of Real-Time Support, Analysis, and Advancements in ROS 2}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:37},
  ISSN =	{2199-2002},
  year =	{2026},
  volume =	{11},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.11.1.1},
  URN =		{urn:nbn:de:0030-drops-257914},
  doi =		{10.4230/LITES.11.1.1},
  annote =	{Keywords: ROS 2, middleware, real-time, timing predictability, publish-subscribe}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.14
A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma

Authors: Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, and Meirav Zehavi

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We present an algorithm for a class of n-fold ILPs whose existing algorithms in literature are often either (1) based on the augmentation framework where one starts with an arbitrary solution and then iteratively moves towards an optimal solution by solving appropriate programs; or (2) require solving a linear relaxation of the program; or (3) are based on decomposition/proximity based arguments. Combinatorial n-fold ILPs is a class of n-fold ILPs introduced and studied by Knop et al. [MP2020] that captures several other problems in a variety of domains. We present a simple and direct algorithm that solves combinatorial n-fold ILPs with unbounded non-negative variables via an application of the Steinitz lemma. Depending on the structure of the input ILP, we also improve upon the existing algorithms in the literature in terms of the running time, thereby showing an improvement that mirrors the one shown by Rohwedder [ICALP2025] contemporaneously and independently.
Cite as

Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, and Meirav Zehavi. A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.IPEC.2025.14,
  author =	{Gupta, Sushmita and Jain, Pallavi and Seetharaman, Sanjay and Zehavi, Meirav},
  title =	{{A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.14},
  URN =		{urn:nbn:de:0030-drops-251467},
  doi =		{10.4230/LIPIcs.IPEC.2025.14},
  annote =	{Keywords: n-fold integer linear program, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.23
Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes

Authors: Archit Chauhan, Samir Datta, and M. Praveen

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Constructing a Depth First Search (DFS) tree is a fundamental graph problem, whose parallel complexity is still not settled. Reif showed parallel intractability of lex-first DFS. In contrast, randomized parallel algorithms (and more recently, deterministic quasipolynomial parallel algorithms) are known for constructing a DFS tree in general (di)graphs. However a deterministic parallel algorithm for DFS in general graphs remains an elusive goal. Working towards this, a series of works gave deterministic NC algorithms for DFS in planar graphs and digraphs. We further extend these results to more general graph classes, by providing NC algorithms for (di)graphs of bounded genus, and for undirected H-minor-free graphs where H is a fixed graph with at most one crossing. For the case of (di)graphs of bounded treewidth, we further improve the complexity to a Logspace bound. Constructing a maximal path is a simpler problem (that reduces to DFS) for which no deterministic parallel bounds are known for general graphs. For planar graphs a bound of O(log n) parallel time on a CRCW PRAM (thus in NC²) is known. We improve this bound to Logspace.
Cite as

Archit Chauhan, Samir Datta, and M. Praveen. Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chauhan_et_al:LIPIcs.FSTTCS.2025.23,
  author =	{Chauhan, Archit and Datta, Samir and Praveen, M.},
  title =	{{Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.23},
  URN =		{urn:nbn:de:0030-drops-251041},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.23},
  annote =	{Keywords: Parallel Complexity, Graph Algorithms, Depth First Search, Maximal Path, Planar Graphs, Minor-Free, Treewidth, Logspace}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.24
Computational Geometry with Probabilistically Noisy Primitive Operations

Authors: David Eppstein, Michael T. Goodrich, and Vinesh Sridhar

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability.
Cite as

David Eppstein, Michael T. Goodrich, and Vinesh Sridhar. Computational Geometry with Probabilistically Noisy Primitive Operations. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.WADS.2025.24,
  author =	{Eppstein, David and Goodrich, Michael T. and Sridhar, Vinesh},
  title =	{{Computational Geometry with Probabilistically Noisy Primitive Operations}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.24},
  URN =		{urn:nbn:de:0030-drops-242552},
  doi =		{10.4230/LIPIcs.WADS.2025.24},
  annote =	{Keywords: Computational geometry, noisy comparisons, random walks}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.26
Computational Complexity of Covering Regular Trees

Authors: Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A graph covering projection, also referred to as a locally bijective homomorphism, is a mapping between the vertices and edges of two graphs that preserves incidences and is a local bijection. This concept originates in topological graph theory but has also found applications in combinatorics and theoretical computer science. In this paper we consider undirected graphs in the most general setting - graphs may contain multiple edges, loops, and semi-edges. This is in line with recent trends in topological graph theory and mathematical physics. We advance the study of the computational complexity of the H-Cover problem, which asks whether an input graph allows a covering projection onto a parameter graph H. The quest for a complete characterization started in 1990’s. Several results for simple graphs or graphs without semi-edges have been known, the role of semi-edges in the complexity setting has started to be investigated only recently. One of the most general known NP-hardness results states that H-Cover is NP-complete for every simple connected regular graph of valency greater than two. We complement this result by considering regular graphs H arising from connected acyclic graphs by adding semi-edges. Namely, we prove that any graph obtained by adding semi-edges to the vertices of a tree making it a d-regular graph with d ≥ 3, defines an NP-complete graph covering problem. In line with the so called Strong Dichotomy Conjecture, we prove that the NP-hardness holds even for simple graphs on input.
Cite as

Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl. Computational Complexity of Covering Regular Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2025.26,
  author =	{Bok, Jan and Fiala, Ji\v{r}{\'\i} and Jedli\v{c}kov\'{a}, Nikola and Kratochv{\'\i}l, Jan},
  title =	{{Computational Complexity of Covering Regular Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.26},
  URN =		{urn:nbn:de:0030-drops-241338},
  doi =		{10.4230/LIPIcs.MFCS.2025.26},
  annote =	{Keywords: graph cover, covering projection, semi-edges, multigraphs, complexity, constrained homomorphisms, trees}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.9
DAMA: A Dual Arbitration Mechanism for Mixed-Criticality Applications

Authors: Wafic Lawand and Rodolfo Pellizzoni

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

Abstract
We discuss hardware resource management in mixed-criticality systems, where requestors may issue latency-critical (LTC) and non-latency-critical (NLTC) requests. LTC requests must adhere to strict latency bounds imposed by safety-critical applications, but timely servicing NLTC requests is necessary to maximize overall system performance in the average case. In this paper, we address this tradeoff for a shared memory resource by proposing DAMA, a dual arbitration mechanism that imposes an upper bound on the cumulative latency of LTC requests without unduly impacting NLTC performance. DAMA comprises a high-performance arbiter, a real-time arbiter, and a mechanism that constantly monitors the cumulative latency of requests suffered by each requestor. DAMA primarily executes in high-performance mode and only switches to real-time mode in the rare instances when its incorporated mechanism detects a violation of a task’s timing guarantee. We demonstrate the effectiveness of our arbitration scheme by adapting a predictable prefetcher that issues NLTC requests and attaching it to the L1 caches of our cores. We show both formally and experimentally that DAMA provides timing guarantees for LTC requests while processing other NLTC requests. We also demonstrate that with a negligible overhead of less than 1.5% on the cumulative latency bound of LTC requests, DAMA can achieve an equivalent average performance to a prefetcher that processes requests under a high-performance arbitration scheme.
Cite as

Wafic Lawand and Rodolfo Pellizzoni. DAMA: A Dual Arbitration Mechanism for Mixed-Criticality Applications. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lawand_et_al:LIPIcs.ECRTS.2025.9,
  author =	{Lawand, Wafic and Pellizzoni, Rodolfo},
  title =	{{DAMA: A Dual Arbitration Mechanism for Mixed-Criticality Applications}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{9:1--9:24},
  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.9},
  URN =		{urn:nbn:de:0030-drops-235875},
  doi =		{10.4230/LIPIcs.ECRTS.2025.9},
  annote =	{Keywords: Real-time Systems, Mixed-criticality Applications, Memory controllers, Prefetchers}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.34
On the Degree Automatability of Sum-Of-Squares Proofs

Authors: Alex Bortolotti, Monaldo Mastrolilli, and Luis Felipe Vargas

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The Sum-of-Squares (SoS) hierarchy, also known as Lasserre hierarchy, has emerged as a promising tool in optimization. However, it remains unclear whether fixed-degree SoS proofs can be automated [O'Donnell (2017)]. Indeed, there are examples of polynomial systems with bounded coefficients that admit low-degree SoS proofs, but these proofs necessarily involve numbers with an exponential number of bits, implying that low-degree SoS proofs cannot always be found efficiently. A sufficient condition derived from the Nullstellensatz proof system [Raghavendra and Weitz (2017)] identifies cases where bit complexity issues can be circumvented. One of the main problems left open by Raghavendra and Weitz is proving any result for refutations, as their condition applies only to polynomial systems with a large set of solutions. In this work, we broaden the class of polynomial systems for which degree-d SoS proofs can be automated. To achieve this, we develop a new criterion and we demonstrate how our criterion applies to polynomial systems beyond the scope of Raghavendra and Weitz’s result. In particular, we establish a separation for instances arising from Constraint Satisfaction Problems (CSPs). Moreover, our result extends to refutations, establishing that polynomial-time refutation is possible for broad classes of polynomial time solvable constraint problems, highlighting a first advancement in this area.
Cite as

Alex Bortolotti, Monaldo Mastrolilli, and Luis Felipe Vargas. On the Degree Automatability of Sum-Of-Squares Proofs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bortolotti_et_al:LIPIcs.ICALP.2025.34,
  author =	{Bortolotti, Alex and Mastrolilli, Monaldo and Vargas, Luis Felipe},
  title =	{{On the Degree Automatability of Sum-Of-Squares Proofs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{34:1--34:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.34},
  URN =		{urn:nbn:de:0030-drops-234110},
  doi =		{10.4230/LIPIcs.ICALP.2025.34},
  annote =	{Keywords: Sum of squares, Polynomial calculus, Polynomial ideal membership, Polymorphisms, Gr\"{o}bner basis theory, Constraint satisfaction problems, Proof complexity}
}
Document
DOI: 10.4230/OASIcs.NG-RES.2025.2
Low-Latency Real-Time Applications on Heterogeneous MPSoCs

Authors: Nicolas Coppik, Pascal Becker, and Marcus Ritter

Published in: OASIcs, Volume 128, Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)

Abstract
Heterogeneous Multi-Processor Systems-on-Chip (MPSoCs) that combine multiple, heterogeneous processing units are becoming increasingly popular for a wide range of applications, including industrial applications, where complex real-time applications can benefit from the performance and flexibility they offer. However, deploying real-time applications with low latency requirements across multiple processing units on such MPSoCs remains a challenging problem, particularly when communication between processors is required on a time-critical path. Existing solutions generally rely on the presence of at least one full-featured, general-purpose operating system on the device, and do not cater to the requirements of distributed, low-latency real-time applications. In this paper, we investigate the performance, with a focus on latency, of different options for communication between CPUs, including inter-processor interrupts and shared memory communication via different memories, on the popular Xilinx Zynq UltraScale+ platform and propose a novel solution for communication between heterogeneous processing units that relies only on the availability of shared memory. Our solution is capable of achieving sub-microsecond latencies for signaling and the transfer of small amounts of data between processing units, making it suitable for deploying distributed, low-latency real-time applications.
Cite as

Nicolas Coppik, Pascal Becker, and Marcus Ritter. Low-Latency Real-Time Applications on Heterogeneous MPSoCs. In Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025). Open Access Series in Informatics (OASIcs), Volume 128, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{coppik_et_al:OASIcs.NG-RES.2025.2,
  author =	{Coppik, Nicolas and Becker, Pascal and Ritter, Marcus},
  title =	{{Low-Latency Real-Time Applications on Heterogeneous MPSoCs}},
  booktitle =	{Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)},
  pages =	{2:1--2:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-366-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{128},
  editor =	{Yomsi, Patrick Meumeu and Wildermann, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2025.2},
  URN =		{urn:nbn:de:0030-drops-229883},
  doi =		{10.4230/OASIcs.NG-RES.2025.2},
  annote =	{Keywords: real-time systems, heterogeneous systems, latency, inter-core communication}
}
Document
DOI: 10.4230/OASIcs.NG-RES.2025.1
Programming Time-Predictable Processors with Lingua Franca

Authors: Magnus Mæhlum, Erling Rennemo Jellum, Shaokai Lin, Marten Lohstroh, Martin Schoeberl, Sverre Hendseth, and Edward A. Lee

Published in: OASIcs, Volume 128, Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)

Abstract
Precision-timed (PRET) machines are an alternative to modern processors that provide precise control over the timing of software execution. This paper describes a platform for developing predictable real-time embedded systems that pair PRET machines with Lingua Franca (LF), a recent reactor-based coordination language with temporal semantics. Specifically, we port LF to FlexPRET, a PRET machine with flexible hardware thread scheduling. We evaluate single-threaded LF with a tight control loop style application on four embedded platforms, including the FlexPRET. The results reveal the underlying platform’s timing variability and how LF plus FlexPRET can remedy this timing variability. Finally, we compare single-threaded to multithreaded LF, again concerning timing. The four embedded platforms used are FlexPRET (bare-metal), RP2040 (bare-metal), nRF52 (with Zephyr), and Raspberry Pi 3b+ (with Linux). Our results indicate that FlexPRET with LF is attractive when precise timing is essential.
Cite as

Magnus Mæhlum, Erling Rennemo Jellum, Shaokai Lin, Marten Lohstroh, Martin Schoeberl, Sverre Hendseth, and Edward A. Lee. Programming Time-Predictable Processors with Lingua Franca. In Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025). Open Access Series in Informatics (OASIcs), Volume 128, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{maehlum_et_al:OASIcs.NG-RES.2025.1,
  author =	{M{\ae}hlum, Magnus and Jellum, Erling Rennemo and Lin, Shaokai and Lohstroh, Marten and Schoeberl, Martin and Hendseth, Sverre and Lee, Edward A.},
  title =	{{Programming Time-Predictable Processors with Lingua Franca}},
  booktitle =	{Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)},
  pages =	{1:1--1:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-366-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{128},
  editor =	{Yomsi, Patrick Meumeu and Wildermann, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2025.1},
  URN =		{urn:nbn:de:0030-drops-229876},
  doi =		{10.4230/OASIcs.NG-RES.2025.1},
  annote =	{Keywords: Real-time systems, time-predictable architecture, embedded system, coordination language}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.93
Polynomials, Divided Differences, and Codes

Authors: S. Venkitesh

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Multiplicity codes (Kopparty et al., J. ACM 2014) are multivariate polynomial codes where the codewords are described by evaluations of polynomials (with a degree bound) and their derivatives up to some order (the multiplicity parameter), on a suitably chosen affine set of points. While efficient decoding algorithms were known in some special cases of point sets, by a reduction to univariate multiplicity codes, a general algorithm for list decoding up to the distance of the code when the point set is an arbitrary finite grid, was obtained only recently (Bhandari et al., IEEE TIT 2023). This required the characteristic of the field to be zero or larger than the degree bound, which is somewhat necessary since list decoding up to distance with small output list size is not possible when the characteristic is significantly smaller than the degree. In this work, we present an alternative construction based on divided differences of polynomials, that conceptually resembles the classical multiplicity codes but has good list decodability "insensitive to the field characteristic". We obtain a simple algorithm that list decodes this code up to distance for arbitrary finite grids over all finite fields. Our construction can also be interpreted as a folded Reed-Muller code, which may be of independent interest.
Cite as

S. Venkitesh. Polynomials, Divided Differences, and Codes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 93:1-93:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{venkitesh:LIPIcs.ITCS.2025.93,
  author =	{Venkitesh, S.},
  title =	{{Polynomials, Divided Differences, and Codes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{93:1--93:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.93},
  URN =		{urn:nbn:de:0030-drops-227216},
  doi =		{10.4230/LIPIcs.ITCS.2025.93},
  annote =	{Keywords: Error-correcting code, polynomial code, Reed-Solomon code, Reed-Muller code, folded Reed-Solomon code, folded Reed-Muller code, multiplicity code, divided difference, q-derivative, polynomial method, list decoding, list decoding capacity, linear algebraic list decoding}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2019.26
Slot-Based Transmission Protocol for Real-Time NoCs - SBT-NoC

Authors: Borislav Nikolić, Robin Hofmann, and Rolf Ernst

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
Network on Chip (NoC) interconnects are some of the most challenging-to-analyse components of multiprocessor platforms. This is primarily due to the following two reasons: (i) NoCs contain numerous shared resources (e.g. routers, links), and (ii) the network traffic often concurrently traverses multiple of those resources. Consequently, complex contention scenarios among traffic flows might occur, some of the important implications being significant performance limitations, and difficulties when performing the real-time analysis. In this work, we propose a slot-based transmission protocol for NoCs (called SBT-NoC), and an accompanying analysis method for deriving worst-case traffic latencies. The cornerstone of SBT-NoC is a contention-less slot-based transmission, arbitrated via a protocol running on a dedicated network medium. The main advantage of SBT-NoC is that, while not requiring any sophisticated hardware support (e.g. virtual channels, a flit-level arbitration), it makes NoCs amenable to real-time analysis and guarantees bounded low latencies of high-priority time-critical flows, which is a sine qua non for the inclusion of NoCs, and multiprocessors in general, in the real-time domain. The experimental evaluation, including both synthetic workloads and a use-case of an autonomous driving vehicle application, reveals that SBT-NoC offers a plethora of configuration opportunities, which makes it applicable to a wide range of diverse traffic workloads.
Cite as

Borislav Nikolić, Robin Hofmann, and Rolf Ernst. Slot-Based Transmission Protocol for Real-Time NoCs - SBT-NoC. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nikolic_et_al:LIPIcs.ECRTS.2019.26,
  author =	{Nikoli\'{c}, Borislav and Hofmann, Robin and Ernst, Rolf},
  title =	{{Slot-Based Transmission Protocol for Real-Time NoCs - SBT-NoC}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.26},
  URN =		{urn:nbn:de:0030-drops-107633},
  doi =		{10.4230/LIPIcs.ECRTS.2019.26},
  annote =	{Keywords: Real-Time Systems, Embedded Systems, Network-on-Chip, Protocols}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ASD.2019
OASIcs, Volume 68, ASD'19, Complete Volume

Authors: Selma Saidi, Rolf Ernst, and Dirk Ziegenbein

Published in: OASIcs, Volume 68, Workshop on Autonomous Systems Design (ASD 2019)

Abstract
OASIcs, Volume 68, ASD'19, Complete Volume
Cite as

Workshop on Autonomous Systems Design (ASD 2019). Open Access Series in Informatics (OASIcs), Volume 68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{saidi_et_al:OASIcs.ASD.2019,
  title =	{{OASIcs, Volume 68, ASD'19, Complete Volume}},
  booktitle =	{Workshop on Autonomous Systems Design (ASD 2019)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-102-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{68},
  editor =	{Saidi, Selma and Ernst, Rolf and Ziegenbein, Dirk},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ASD.2019},
  URN =		{urn:nbn:de:0030-drops-103628},
  doi =		{10.4230/OASIcs.ASD.2019},
  annote =	{Keywords: Hardware, Analysis and design of emerging devices and systems, Computer systems organization, Robotic autonomy, Software and its engineering, Software safety, Dependable and fault-tolerant systems and networks}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ASD.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Selma Saidi, Rolf Ernst, and Dirk Ziegenbein

Published in: OASIcs, Volume 68, Workshop on Autonomous Systems Design (ASD 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

Workshop on Autonomous Systems Design (ASD 2019). Open Access Series in Informatics (OASIcs), Volume 68, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{saidi_et_al:OASIcs.ASD.2019.0,
  author =	{Saidi, Selma and Ernst, Rolf and Ziegenbein, Dirk},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Workshop on Autonomous Systems Design (ASD 2019)},
  pages =	{0:i--0:xviii},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-102-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{68},
  editor =	{Saidi, Selma and Ernst, Rolf and Ziegenbein, Dirk},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ASD.2019.0},
  URN =		{urn:nbn:de:0030-drops-103337},
  doi =		{10.4230/OASIcs.ASD.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.ASD.2019.1
Fault-Tolerance by Graceful Degradation for Car Platoons

Authors: M. Baha E. Zarrouki, Verena Klös, Markus Grabowski, and Sabine Glesner

Published in: OASIcs, Volume 68, Workshop on Autonomous Systems Design (ASD 2019)

Abstract
The key advantage of autonomous car platoons are their short inter-vehicle distances that increase traffic flow and reduce fuel consumption. However, this is challenging for operational and functional safety. If a failure occurs, the affected vehicles cannot suddenly stop driving but instead should continue their operation with reduced performance until a safe state can be reached or, in the case of temporal failures, full functionality can be guaranteed again. To achieve this degradation, platoon members have to be able to compensate sensor and communication failures and have to adjust their inter-vehicle distances to ensure safety. In this work, we describe a systematic design of degradation cascades for sensor and communication failures in autonomous car platoons using the example of an autonomous model car. We describe our systematic design method, the resulting degradation modes, and formulate contracts for each degradation level. We model and test our resulting degradation controller in Simulink/Stateflow.
Cite as

M. Baha E. Zarrouki, Verena Klös, Markus Grabowski, and Sabine Glesner. Fault-Tolerance by Graceful Degradation for Car Platoons. In Workshop on Autonomous Systems Design (ASD 2019). Open Access Series in Informatics (OASIcs), Volume 68, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{zarrouki_et_al:OASIcs.ASD.2019.1,
  author =	{Zarrouki, M. Baha E. and Kl\"{o}s, Verena and Grabowski, Markus and Glesner, Sabine},
  title =	{{Fault-Tolerance by Graceful Degradation for Car Platoons}},
  booktitle =	{Workshop on Autonomous Systems Design (ASD 2019)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-102-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{68},
  editor =	{Saidi, Selma and Ernst, Rolf and Ziegenbein, Dirk},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ASD.2019.1},
  URN =		{urn:nbn:de:0030-drops-103344},
  doi =		{10.4230/OASIcs.ASD.2019.1},
  annote =	{Keywords: fault-tolerance, degradation, car platoons, autonomous driving, contracts}
}
  • Refine by Type
  • 34 Document/PDF
  • 9 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 1 2026
  • 9 2025
  • 13 2019
  • 2 2018
  • 3 2017
  • Show More...

  • Refine by Author
  • 11 Ernst, Rolf
  • 3 Quinton, Sophie
  • 2 Ivers, Matthias
  • 2 Saidi, Selma
  • 2 Schliecker, Simon
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs
  • 15 OASIcs
  • 5 LITES
  • 1 DagRep
  • 1 DagSemRep
  • Show More...

  • Refine by Classification
  • 4 Computer systems organization → Embedded and cyber-physical systems
  • 4 Computer systems organization → Real-time systems
  • 3 Computer systems organization → Embedded systems
  • 2 Computer systems organization → Self-organizing autonomic computing
  • 2 General and reference → General literature
  • Show More...

  • Refine by Keyword
  • 3 real-time systems
  • 2 FPGA
  • 2 Fixed priority
  • 2 Real-time systems
  • 2 fault-tolerance
  • 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