HYPE with stochastic events

Luca Bortolussi, Vashti Galpin, Jane Hillston

TL;DR

This paper extends the HYPE process algebra to include stochastic events, allowing researchers to model hybrid systems where discrete changes occur at random intervals. By providing a formal mapping to Transition-Driven Stochastic Hybrid Automata (TDSHA), the authors enable quantitative analysis and simulation of complex systems that blend continuous physical flows with probabilistic triggers.

What Problem Does This Paper Address?

Modeling "hybrid systems"—those that combine continuous evolution (like temperature or chemical concentrations) with discrete events (like flipping a switch)—is notoriously difficult. The HYPE process algebra was previously introduced to handle this by modeling individual "influences" or "flows" separately and then composing them.

However, the original version of HYPE had a limitation: discrete events were either "urgent" (happening the instant a condition was met) or "non-urgent" (happening after some undefined, non-deterministic delay). This lack of precision for non-urgent events made it impossible to perform quantitative analysis, such as calculating the probability of a system failure or the expected time for a task to complete. This paper addresses that gap by replacing vague non-urgent events with precisely defined stochastic events.

Methods

The authors introduce a stochastic extension to HYPE and define its semantics through a multi-step formal process:

  1. Stochastic Actions: Instead of an undefined delay, non-urgent actions are now governed by a probability distribution (specifically, an exponential distribution with a defined rate function).
  2. Compositional Mapping: The paper defines how to translate HYPE subcomponents and controllers into Transition-Driven Stochastic Hybrid Automata (TDSHA).
  3. Uncontrolled System: Represents the physical flows (e.g., a heater's effect on temperature).
  4. Controller: Represents the logic and causality (e.g., the thermostat's rules).
  5. Synchronized Product: The authors provide a mathematical way to "multiply" these individual automata together to create a single, unified model of the entire system.
  6. PDMP Semantics: Finally, these TDSHAs serve as an intermediary to map HYPE models onto Piecewise Deterministic Markov Processes (PDMPs), a well-studied class of stochastic processes that can be analyzed using existing mathematical tools.

Datasets

Not discussed in the paper. The authors evaluate their approach using a synthetic "running example" of an orbiter (satellite) that must regulate its temperature while periodically downloading data to Earth.

Key Insights and Ideas

  • Fine-Grained Modeling: Unlike other hybrid process algebras that require you to write complex Ordinary Differential Equations (ODEs) for every possible state of a system, HYPE allows you to model individual "influences" (like "sunlight" or "insulation") in isolation. The complex global behavior emerges automatically when these influences are composed.
  • Stochasticity as a Refinement: By treating non-urgent events as stochastic, the authors transform HYPE from a qualitative modeling tool into a quantitative one. This allows for "rate functions" that depend on the state of the system (e.g., a data download takes longer if the satellite is too hot).
  • Separation of Concerns: The architecture clearly separates the "uncontrolled system" (the physics) from the "controller" (the logic), making the models easier to build, debug, and extend.

Key Results

The paper demonstrates the power of the new framework through the Orbiter Example:

  • Dynamic Rates: They successfully modeled a scenario where the rate of a stochastic event (data downloading) is not constant but changes based on a continuous variable (temperature).
  • Sampled Trajectories: The authors provide sampled trajectories (simulations) showing how data accumulates linearly and is then cleared by stochastic download events, illustrating the "hybrid" nature of the system.
  • Formal Rigor: The primary result is the formal definition of the mapping from HYPE to TDSHA, proving that the compositionality of the language is preserved in the stochastic setting.

Limitations and Future Work

  • State Explosion: The current method for building the automata can generate many "unreachable states." While these can be pruned, a more efficient construction method would be beneficial to avoid combinatorial explosion in very large systems.
  • Well-Behavedness: It is theoretically possible to create a model where an infinite number of instantaneous events fire at the same moment (Zeno behavior). Checking for this is "undecidable" in the general case, though the authors suggest stricter, decidable subsets of the language can avoid this.
  • Stochastic Resets: Currently, only the timing of events is stochastic. The authors suggest that future versions should allow the outcome of an event (the "reset") to be stochastic as well (e.g., a component might break with a 5% probability when switched on).
  • Tooling: The authors aim to implement an efficient simulator specifically for stochastic HYPE to move beyond theoretical modeling into practical engineering applications.

Summary updated

BibTeX
@inproceedings{bortolussi2011hype,
  author = {Luca Bortolussi and Vashti Galpin and Jane Hillston},
  title = {{HYPE with stochastic events}},
  booktitle = {QAPL},
  year = {2011},
  url = {https://openreview.net/forum?id=pBeSGqWTHO},
}

Loading related content...

Figure