Pacing Types for Asynchronous Stream Equations
Florian Kohn, Arthur Correnson, Jan Baumeister, Bernd Finkbeiner · 2026
Read Pacing Types for Asynchronous Stream Equations by Florian Kohn, Arthur Correnson, Jan Baumeister, Bernd Finkbeiner (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26635.txt.
Introduction
Florian Kohn and three others add a type system that catches timing clashes in stream monitors for sensors. Monitors blend sensor streams that arrive at uneven speeds. Pacing notes let users state sync rules, yet users can demand sync that can never hold. Pacing types check those notes against a formal meaning for a core slice of RTLola and prove monitors free of timing mismatch. The soundness proof itself was machine-checked with the Rocq assistant, adding a second layer of assurance.
Catalog record
| CREATOR | Florian Kohn, Arthur Correnson, Jan Baumeister, Bernd Finkbeiner |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51993 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.26635
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pacing Types for Asynchronous Stream Equations Florian Kohn, Arthur Correnson, Jan Baumeister, Bernd Finkbeiner Abstract Stream-based monitoring is a runtime verification approach where a monitor aggregates streams of input data from sensors and other sources to give real-time statistics and assessments of a system’s health. One of the central challenges in designing reliable stream-based monitors is to deal with the asynchronous nature of data streams: in concrete applications, the different sensors being monitored produce values at different speeds, and it is the monitor’s responsibility to correctly react to the asynchronous arrival of different streams of values. To ease this process, modern frameworks for stream-based monitoring such as RTLola enable users to finely specify data synchronization policies via a system of pacing annotations . While this feature simplifies the design of monitors, it can also lead users to write inconsistent policies, where synchronization between two streams is explicitly requested via annotations, but cannot always be achieved. To mitigate this issue, this paper presents pacing types , a novel type system implemented in RTLola to ensure that monitors for asynchronous streams are free of timing inconsistencies. We give a formal semantics to pacing annotations for a core fragment of RTLola , and present a soundness proof of the pacing type system. For an additional level of guarantees, we machine-checked the soundness proof using the Rocq proof assistant. 1 Introduction Runtime verification is a safety assurance mechanism in which systems are monitored during their execution. Runtime verification is particularly useful for increasing the reliability of complex cyber-physical systems (CPS) for which obtaining a model for static verification is difficult or impossible. Stream-based monitoring is an approach to runtime verification in which a monitor collects data through input streams, which are then combined and aggregated in output streams to give real-time assessments of a system’s health. While, there exist many formalisms and programming languages to describe stream-based monitors [ 11 , 13 , 3 , 20 , 15 , 23 ] , we focus on the stream-based specification language RTLola . In RTLola , a monitor is specified by listing equations relating input and output streams. Certain boolean output streams, called triggers, indicate whether the system being monitored is behaving as expected. From a system perspective, monitors are passive components. They react to inputs from the system as they arrive. If different system sensors generate inputs at varying rates, the monitor must handle the asynchronous arrival of data. To simplify this process, RTLola features a system of pacing annotations where each output stream is labeled with additional information indicating when a stream must produce a fresh value in reaction to the asynchronous arrival of new input values. While the pacing annotation system of RTLola has proven to be useful in practical applications [ 12 , 5 , 3 ] , it also introduces a critical challenge: ensuring the consistency of pacing annotations. Indeed, it is easy to write annotations that are incompatible with one another or that over-constrain a stream by requiring it to produce values at times when its dependencies are not guaranteed to be available. Ensuring consistency of pacing annotations is all the more difficult because the semantics of RTLola ’s pacing annotations have, thus far, never been rigorously formalized. In this paper, we address this issue in two ways. We propose the first formal semantics of RTLola ’s pacing annotations, and we present a type system to check the consistency of pacing annotations. Contributions In summary, we make the following contributions: 1. We formalize the essence of RTLola ’s system of pacing annotations. In particular, we give a formal semantics to stream equations decorated with pacing annotations. 2. We present a type system to check the consistency of pacing annotations, and formally prove its soundness. Concretely, we prove that well-typed annotated equations have at least one solution. 3. Finally, to obtain an additional level of reliability, we machine-checked the correctness proof of the type system using the Rocq proof assistant. Structure of the paper Section 2 provides an overview of RTLola and its system of pacing annotations. It also illustrates the inconsistency problem. Section 3 formalizes semantics of pacing annotations for a core fragment of RTLola , and introduces a type system to check consistency of pacing annotations. Section 5 presents a soundness proof of the type system. Finally, Section 6 describes two extensions of the type system. 1.1 Related Work Runtime verification has been studied since the late 90s [ 21 ] . Specifications are often expressed in temporal logics such as LTL [ 2 ] and MTL [ 1 ] . Applications include Markov Decision Processes [ 19 , 17 ] , cyber-physical systems [ 3 ] , and software [ 18 ] . Stream-based monitoring framework like Lola [ 11 ] , RTLola [ 4 ] , Tessla [ 20 ] , and HStriver [ 15 ] provide expressive specification languages coupled with efficient monitoring infrastructures. Synchronous programming languages such as LUSTRE [ 16 ] , ESTEREL [ 8 ] , and Zélus [ 7 ] share similarities with stream-based languages for monitoring. In particular, both paradigms need to address timing inconsistencies (ensuring that values exists when they are requested). Synchronous languages use notions of clocks [ 14 , 10 , 22 ] , and associated static analyses to resolve timing issues. We propose a type analysis to address the timing inconsistencies introduced by the expressive pacing annotations of RTlola . We note that type-based approach have already been explored in similar contexts. For example, [ 6 ] introduces type systems to detect non-causal equations, a property related to the existence of models in stream-based monitoring. Other type systems address additional program properties; for example, MARVeLus employs a refinement type system that reasons about temporal behavior using LTL [ 24 ] specifications [ 9 ] . 2 Asynchronous Streams in RTLola This section provides a high-level overview of RTLola and its pacing annotations using a battery management system as an example. In RTLola , monitors are specified by declaring a list of named input and output streams. As an example, consider the following RTLola specification which monitors excessive power draw: ⬇ 1 input battery_lvl 2 output drain := battery_lvl . prev ( or : battery_lvl ) - battery_lvl 3 output warning := drain > 5 The input stream battery_lvl captures the current battery level measurement. The output stream drain computes the charge loss by subtracting the current battery level from the previous one, accessed via battery_lvl . prev ( or :...) . The argument after or : provides a default value for the first evaluation step. This example illustrates the core concepts of input and output streams and the use of stream offsets to express temporal properties. In practice, a monitor often requires access to multiple sensors to produce meaningful verdicts about the system’s health. For example, the previous specification can be refined to monitor that the battery does not overheat while it is charging. For this, an additional input stream temperature captures the current temperature of the battery being monitored: ⬇ 1 input battery_lvl : Int 2 input temperature : Int 3 output drain := battery_lvl . prev ( or : battery_lvl ) - battery_lvl 4 output