Verification of Probabilistic Real Time Systems

22 concepts17 papers1 proposal

Modern cyber-physical systems—ranging from autonomous vehicles to medical devices—operate under two inescapable realities: physical time and stochastic uncertainty. To verify that an automated braking system will prevent a collision, it is not enough to prove it works eventually; it must work within a strict real-time deadline (e.g., 50 milliseconds). Furthermore, because sensors are noisy and hardware components occasionally fail, this guarantee must often be quantitative: "The probability of failing to brake within 50ms is less than $10^{-6}$."

Combining continuous time, non-deterministic environmental choices, and discrete probabilistic events creates an mathematical perfect storm. The state space becomes uncountably infinite, rendering traditional exhaustive model checking intractable. Over the past few decades, researchers have developed a suite of techniques to unify these domains, moving from exact symbolic verification to game-theoretic abstractions, statistical sampling, and ultimately, real-time programming languages.

The Core Challenge: Time, Chance, and Choice

To understand why verifying these systems is difficult, consider the three distinct types of behavior they exhibit simultaneously:

  1. Continuous Time: Clocks advance continuously and smoothly ($\Delta t \in \mathbb{R}_{\ge 0}$).
  2. Probabilistic Choice: Random events occur according to known distributions (e.g., a message has a 10% chance of being dropped).
  3. Non-deterministic Choice: Unpredictable environmental inputs or concurrent process interleavings where probabilities are unknown.

The standard formalism for capturing this interplay is the Probabilistic Timed Automaton (PTA). In a PTA, state transitions can depend on continuous clock variables, but the outcome of a transition is probabilistic.

As Marta Z. Kwiatkowska et al. demonstrate in Symbolic Computation of Maximal Probabilistic Reachability, computing the exact maximum probability of reaching a target state requires symbolic state exploration. Because time is continuous, we cannot visit every state individually. Instead, symbolic verification groups infinite sets of clock configurations into geometric shapes called zones or regions, using predecessor and intersection operations to compute reachability bounds across the infinite state space.

Taming Non-Determinism with Stochastic Games

When non-determinism and probability mix, we cannot simply ask "what is the probability of failure?" because the probability depends on how the non-deterministic choices are resolved. Instead, we must compute the worst-case (maximal) or best-case (minimal) probability across all possible choices.

This formulation maps perfectly to stochastic games. In this framing, the system's non-determinism is treated as a player (the scheduler or controller) playing a game against nature (the probabilistic choices).

               [ Current State ]
                       │
         ┌─────────────┴─────────────┐
         ▼                           ▼
  Choice A (Non-det)          Choice B (Non-det)
  [Player 1: Controller]      [Player 1: Controller]
         │                           │
   ┌─────┴─────┐               ┌─────┴─────┐
   ▼ (60%)     ▼ (40%)         ▼ (10%)     ▼ (90%)
Success     Failure         Success     Failure
   [Player 2: Nature]          [Player 2: Nature]

In Stochastic Games for Verification of Probabilistic Timed Automata, Marta Z. Kwiatkowska et al. showed that a PTA can be abstracted into a finite-state, two-player stochastic game. By solving this game, verifiers can determine the exact bounds of what a system can achieve under the worst possible environmental conditions.

This game-theoretic approach has been extended to solve several complex variations of the problem:

Scaling Up via Statistical Sampling and Abstraction

While symbolic methods and stochastic games provide exact mathematical answers, they suffer from the curse of dimensionality when applied to networks of interacting components. To make verification practical for real-world systems, the community developed two primary scaling strategies: structural abstractions and statistical sampling.

Structural Abstractions

Instead of tracking every individual clock and variable, we can build a simpler model that preserves the core behaviors. For example, Paolo Ballarini et al. introduced "stochastic state classes" in Transient Analysis of Networks of Stochastic Timed Automata Using Stochastic State Classes to track how probability distributions evolve over continuous time across synchronized components. For continuous-state systems, Sadegh Esmaeil Zadeh Soudjani et al. leveraged Dynamic Bayesian Networks in Dynamic Bayesian Networks as Formal Abstractions of Structured Stochastic Processes to exploit the inherent conditional independence of system components, creating compact formal abstractions that bypass state explosion.

Statistical Model Checking (SMC)

When a system is too complex to abstract or represent symbolically, we can treat it as a black-box simulator and execute random sample paths. As reviewed by Kim G. Larsen et al. in Statistical Model Checking: Past, Present, and Future, SMC uses statistical techniques like hypothesis testing and estimation to provide probabilistic guarantees (e.g., "we are 99.9% confident that the failure probability is below 0.001").

The core challenge of SMC is sample efficiency—rare failures require millions of simulations to detect. To solve this, Nima Roohi et al. developed STMC, a tool detailed in STMC: Statistical Model Checker with Stratified and Antithetic Sampling. By using stratified sampling (ensuring rare regions of the state space are explicitly targeted) and antithetic sampling (generating negatively correlated simulation paths), the authors significantly reduced the variance of the statistical estimators, making the verification of large-scale probabilistic systems practical.

From Verification to Execution: Real-Time Probabilistic Programming

For a long time, a strict wall existed between verification formalisms (like PTAs) and actual software implementation. Developers writing code for autonomous systems had to manually implement probabilistic inference algorithms (like particle filters for localization) and manually configure real-time task schedules. This disconnect frequently introduced bugs, as expensive probabilistic calculations could cause a task to miss its real-time deadline.

To bridge this gap, Lars Hummelgren et al. introduced Real-Time Probabilistic Programming Languages (RTPPLs) in Real-time probabilistic programming. Their language, ProbTime, natively integrates timing constraints with probabilistic execution.

The key insight behind an RTPPL is resource-adaptive inference. If a probabilistic algorithm (like a particle filter) is running out of time as a hard real-time deadline approaches, the runtime environment automatically adjusts its parameters (such as dynamically lowering the particle count).

[ High Time Remaining ] ──► Run Inference with 10,000 Particles ──► High Accuracy
[ Deadline Approaching ] ──► Run Inference with 1,000 Particles  ──► Lower Accuracy, Meets Deadline

By introducing concepts like "execution-time fairness," the language ensures that the system degrades its mathematical accuracy gracefully rather than missing a critical real-time deadline, bringing the foundational principles of timed-probabilistic modeling directly into the execution loop of physical systems.

Key Foundational Work

Symbolic Computation of Maximal Probabilistic Reachability (2001) — contributed 2 concept elements to this direction.
Computing Probability Bounds for Linear Time Formulas over Concurrent Probabilistic Systems (1998) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_probabilistic_real_time_systems_22363ded,
  title = {probabilistic real-time systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-real-time-systems/rdr_22363ded9fe44b3ca3841cc8f4931d57},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_probabilistic_real_time_systems_22363ded_v1,
  title = {probabilistic real-time systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-real-time-systems/rdr_22363ded9fe44b3ca3841cc8f4931d57/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake