Model Checking for a Probabilistic Branching Time Logic with Fairness

Christel BaierChristel Baier, Marta Z. KwiatkowskaMarta Z. Kwiatkowska

DOI Link

Christel Baier, Marta Z. Kwiatkowska
Model Checking for a Probabilistic Branching Time Logic with Fairness
Distributed Computing, 11(3):125--155, 1998

Details
Bibtex

KurzfassungAbstract
We consider concurrent probabilistic systems, based on probabilistic automata of Segala & Lynch [55], which allow non-deterministic choice between probability distributions. These systems can be decomposed into a collection of “computation trees” which arise by resolving the non-deterministic, but not probabilistic, choices. The presence of non-determinism means that certain liveness properties cannot be established unless fairness is assumed. We introduce a probabilistic branching time logic PBTL, based on the logic TPCTL of Hansson [30] and the logic PCTL of [55], resp. pCTL [14]. The formulas of the logic express properties such as “every request is eventually granted with probability at least p”. We give three interpretations for PBTL on concurrent probabilistic processes: the first is standard, while in the remaining two interpretations the branching time quantifiers are taken to range over a certain kind of fair computation trees. We then present a model checking algorithm for verifying whether a concurrent probabilistic process satisfies a PBTL formula assuming fairness constraints. We also propose adaptations of existing model checking algorithms for pCTL* [4, 14] to obtain procedures for PBTL under fairness constraints. The techniques developed in this paper have applications in automatic verification of randomized distributed systems.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@article{BK1998,
  author  = {Christel Baier and Marta Z. Kwiatkowska},
  title   = {Model Checking for a Probabilistic Branching Time Logic with
             Fairness},
  journal = {Distributed Computing},
  volume  = {11},
  number  = {3},
  year    = {1998},
  pages   = {125--155},
  doi     = {10.1007/s004460050046}
}