Computing Probability Bounds for Linear Time Formulas over Concurrent Probabilistic Systems

Christel Baier, Marta Z. Kwiatkowska, Gethin NormanPROBMIV 1998 · DOI

TL;DR

This paper introduces a more efficient method for verifying concurrent probabilistic systems against linear time logic formulas. Instead of computing exact probabilities, it calculates lower and upper bounds, providing an interval that contains the true probability. This approach significantly reduces computational complexity, making it more practical for analyzing complex systems.

What Problem Does This Paper Address?

Verifying concurrent probabilistic systems (systems with both randomness and nondeterministic choices) against temporal logic specifications is notoriously difficult. The exact computation of probabilities for these systems is computationally expensive, with time complexity that is doubly exponential in the size of the formula and polynomial in the system size. This high complexity makes it impractical for many real-world applications. The paper aims to alleviate this by providing a method to compute probability bounds rather than exact values, offering a trade-off between precision and computational feasibility.

Methods

The core of the paper's contribution lies in defining algorithms to compute lower and upper bounds for the probability of an LTL formula holding in a given state. These bounds are derived inductively based on the structure of the LTL formula:

  • Atomic Propositions and Boolean Connectives: For atomic propositions, bounds are 0 or 1 based on satisfaction. Conjunctions are handled by taking the maximum of lower bounds (minus 1, to account for potential overlap) and the minimum of upper bounds. Negation is handled by complementing the bounds of the negated formula.
  • Temporal Operators (Next, Until): The "next state" operator (Xf) involves computing weighted sums of bounds from successor states. The "until" operator (f1 U f2) is more complex and is reduced to a fixed-point formulation. This fixed-point problem is then solved using an iterative optimization method, which is non-linear for concurrent systems.

The authors emphasize that their approach is "space-efficient" (linear space complexity for concurrent systems) and offers a "heuristic" that is still sound.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and its application to a case study.

Key Insights and Ideas

  • The Power of Bounds: The paper demonstrates that for many practical purposes, an interval of probabilities (a lower and upper bound) is sufficient, especially as an initial check. This is a significant departure from the need for exact probabilities in many verification tasks.
  • Complexity Trade-off: The core insight is that by sacrificing exactness, one gains substantial computational efficiency. This makes verification of larger and more complex systems tractable.
  • Adversarial Nature: The need for lower and upper bounds is rooted in the presence of nondeterminism, which is modeled by an "adversary" (scheduler). The bounds capture the worst-case and best-case scenarios across all possible adversarial choices.
  • Iterative Optimization: The paper elegantly reduces complex temporal operators like "until" to optimization problems that can be solved iteratively, providing a constructive algorithm.

Key Results

  • Complexity Reduction: The proposed method reduces time complexity from doubly exponential to single exponential for concurrent systems, and space complexity from exponential to linear. For sequential systems, time complexity is reduced to polynomial.
  • Case Study Success: The paper presents a case study on the randomized dining philosophers problem. For certain properties, the lower bound calculation, when iterated until convergence, yielded results that were very close to the exact probability (within a specified error tolerance), effectively providing an accurate estimate.
  • Soundness: The method is proven to be sound, meaning that the computed lower bound is indeed a lower bound for the true probability, and the upper bound is an upper bound.

Limitations and Future Work

  • Error Estimation: The authors acknowledge that they have not been able to estimate the error associated with the lower/upper bound calculations in the general case. While the bounds are sound, the width of the interval ([0,1] in the worst case) can be large.
  • Improving Bounds: Future work could focus on improving the accuracy of the bounds, potentially by locally estimating conditional probabilities or by characterizing subclasses of formulas for which the error is small.
  • MTBDD Efficiency: While MTBDDs show promise for model manipulation, their performance in the case study was poorer than sparse matrices for pure calculations. Further investigation into MTBDD implementation heuristics is suggested.
  • Sequential Systems: For sequential systems, the method offers a time improvement but not a space complexity reduction.

Summary updated

BibTeX
@article{baier1998computing,
  author = {Christel Baier and Marta Z. Kwiatkowska and Gethin Norman},
  title = {{Computing Probability Bounds for Linear Time Formulas over Concurrent Probabilistic Systems}},
  journal = {PROBMIV},
  year = {1998},
  doi = {10.1016/s1571-0661(05)80595-x},
}
Figure