A Faster-Than Relation for Semi-Markov Decision Processes

Mathias Ruggaard Pedersen, Giorgio Bacci, Kim G. LarsenarXiv 2019 · DOI

TL;DR

This paper introduces a formal definition of "faster-than" for semi-Markov decision processes (SMDPs), which are used to model real-time systems. They show that this notion can lead to "parallel timing anomalies" where a faster component doesn't necessarily make the whole system faster, and propose decidable conditions to avoid these anomalies.

What Problem Does This Paper Address?

When designing complex real-time and cyber-physical systems, it's crucial to understand how different components interact and how their performance affects the overall system. A key aspect of performance is timing – how quickly a system can respond or complete a task. The authors are interested in formally defining what it means for one real-time process to be "faster" than another. This is particularly important for reasoning about system design and optimization.

The challenge arises when these systems are built from smaller, concurrently running components. While we might know that component A is faster than component B, when they are combined with a "context" (other parts of the system), replacing B with A doesn't always lead to a faster overall system. This phenomenon is called a "parallel timing anomaly." The paper aims to define "faster-than" formally for SMDPs (a common model for real-time systems) and to identify conditions under which these timing anomalies can be avoided, especially in the context of parallel composition.

Methods

The core of the paper is the definition of a "faster-than" relation for SMDPs. This relation, denoted by $<$, is defined in a reactive manner: process U is faster than process V if, for any sequence of actions, U can execute that sequence within any given time bound with at least the same probability as V. This is a probabilistic comparison, considering all possible schedulers (ways of choosing actions) for both processes.

To analyze the composition of these processes, the authors consider various ways to combine SMDPs in parallel, focusing on how their residence times (how long a process stays in a state) are composed. They then investigate the compositional properties of their "faster-than" relation, showing that it is not a precongruence with respect to parallel composition, which is why timing anomalies can occur.

To address these anomalies, they introduce two conditions: "monotonicity" and "strong monotonicity." These conditions are placed on the interaction between a component and its context. Strong monotonicity, in particular, is shown to be decidable and sufficient to guarantee the absence of parallel timing anomalies. The decidability relies on properties of semialgebraic sets within the theory of real numbers.

Datasets

Not discussed in the paper. The paper focuses on theoretical definitions and properties of SMDPs and their composition, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Reactive "Faster-Than": The paper formalizes "faster-than" in a reactive sense, meaning how quickly a system responds to inputs, which is crucial for real-time systems. This contrasts with "generative" notions that might focus on how quickly a system produces outputs.
  • Timing Anomalies are Inherent: The paper demonstrates that parallel timing anomalies can occur even in systems without non-determinism or probabilistic branching, highlighting that these anomalies are a fundamental consequence of how timing behaviors compose.
  • Compositionality is Tricky: The "faster-than" relation does not compose nicely with parallel execution. This means that if U is faster than V, and W is a context, U || W is not necessarily faster than V || W. This is a significant finding for system design.
  • Decidable Conditions for Anomaly Avoidance: The introduction of "strong monotonicity" provides a concrete, decidable condition that guarantees parallel timing anomalies will not occur. This is a key practical contribution for engineers designing real-time systems.
  • Decidability via Real Number Theory: The decidability of strong monotonicity is achieved by leveraging properties of semialgebraic sets, connecting theoretical computer science with mathematical logic.

Key Results

  • A formal definition of a "faster-than" relation for Semi-Markov Decision Processes (SMDPs) is provided.
  • It is shown that this "faster-than" relation is not compositional with respect to parallel composition, leading to parallel timing anomalies.
  • Examples are given demonstrating parallel timing anomalies for product, minimum, and maximum rate compositions of SMDPs.
  • Conditions for avoiding parallel timing anomalies are introduced, with "strong monotonicity" being a decidable sufficient condition.
  • Theorem 5.12 states that if strong monotonicity holds, parallel timing anomalies are avoided.
  • Theorem 5.14 establishes the decidability of checking strong monotonicity for finite SMDPs.

Limitations and Future Work

  • Non-determinism and Decidability: The authors note that their decidable conditions for avoiding timing anomalies (specifically, strong monotonicity) are quite strict and rule out non-determinism. They acknowledge that obtaining better (less strict) decidable results is challenging because the "faster-than" relation itself can become undecidable when non-determinism is present.
  • Context-Dependent Conditions: The current conditions for avoiding anomalies depend on both the components being swapped and the context. Future work could explore conditions on the context alone that would guarantee anomaly avoidance regardless of the specific components being swapped.
  • Scheduler Memory: The paper primarily considers memoryless schedulers or those that remember actions and states. The behavior of schedulers that can remember time is mentioned as an open question.
  • Exploring Boundaries of Decidability: An interesting future direction is to further explore the boundaries of decidability for conditions that avoid timing anomalies, especially in the presence of non-determinism.

Summary updated

BibTeX
@misc{pedersen2019faster,
  author = {Mathias Ruggaard Pedersen and Giorgio Bacci and Kim G. Larsen},
  title = {{A Faster-Than Relation for Semi-Markov Decision Processes}},
  year = {2019},
  doi = {10.4204/eptcs.312.3},
}
Figure