Name
Abstract | ||
|---|---|---|
We present an approach for applying symmetry reduction techniques to probabilistic model checking, a formal verification method for the quantitative analysis of systems with stochastic characteristics. We target systems with a set of non-trivial, but interchangeable, components such as those which commonly arise in randomised distributed algorithms or probabilistic communication protocols. We show, for three types of probabilistic models, that symmetry reduction, similarly to the non-probabilistic case, allows verification to instead be performed on a bisimilar quotient model which may be up to factorially smaller. We then propose an efficient algorithm for the construction of the quotient model using a symbolic implementation based on multi-terminal binary decision diagrams (MTBDDs) and, using four large case studies, demonstrate that this approach offers not only a dramatic increase in the size of probabilistic model which can be quantitatively analysed but also a significant decrease in the corresponding run-times. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11817963_23 | CAV |
Keywords | Field | DocType |
probabilistic model,formal verification,model checking,distributed algorithm,binary decision diagram,biological systems,quantitative analysis,security protocol,relational data,communication protocol,limiting factor | Divergence-from-randomness model,Model checking,Computer science,Quotient,Binary decision diagram,Algorithm,Theoretical computer science,Probabilistic analysis of algorithms,Statistical model,Probabilistic logic,Formal verification | Conference |
Volume | ISSN | ISBN |
4144 | 0302-9743 | 3-540-37406-X |
Citations | PageRank | References |
64 | 2.19 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marta Z. Kwiatkowska | 1 | 6118 | 322.21 |
| Gethin Norman | 2 | 4163 | 193.68 |
| David Parker | 3 | 4018 | 184.00 |