Undecidability Results for Distributed Probabilistic Systems

TitleUndecidability Results for Distributed Probabilistic Systems
Publication TypeConference Paper
Year of Publication2009
AuthorsGiro, S
Conference NameFormal Methods: Foundations and Applications, 12th Brazilian Symposium on Formal Methods, SBMF 2009
PublisherSpringer
ISBN Number978-3-642-10451-0
AbstractIn the verification of concurrent systems involving probabilities, the aim is to find out the maximum/minimum probability that a given event occurs (examples of such events being “the system reaches a failure state”,“a message is delivered”). Such extremal probabilities are obtained by quantifying over all the possible ways in which the processes may be interleaved. Interleaving choices are considered a particular case of nondeterministic behaviour. Such behaviour is dealt with by considering schedulers that resolve the nondeterministic choices. Each scheduler determines a Markov chain for which actual probabilities can be calculated. In the recent literature on distributed systems, particular attention has been paid to the fact that, in order to obtain accurate results, the analysis must rely on partial information schedulers, instead of full-history dependent schedulers used in the setting of Markov decision processes. In this paper, we present undecidability results for distributed schedulers. These schedulers were devised in previous works, and aim to capture the fact that each process has partial information about the actual state of the system. Some of the undecidability results we present are particularly impressive: in the setting of total information the same problems are inexpensive and, indeed, they are used as preprocessing steps in more general model checking algorithms.
DOI10.1007/978-3-642-10452-7