ISSN:
1432-0452
Keywords:
Key words:Probabilistic processes – Temporal logic – Verification – Fairness
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract. 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004460050046
