Publications
Publications › References ›
2006
Conference papers
Symmetry Reduction for Probabilistic Model Checking
[KNP06a]
Marta Kwiatkowska, Gethin Norman and David Parker.
Symmetry Reduction for Probabilistic Model Checking.
In T. Ball and R. Jones (editors), Proc. 18th International Conference on Computer Aided Verification (CAV'06), volume 4144 of Lecture Notes in Computer Science, pages 234-248, Springer-Verlag.
August 2006.
ps.gz pdf bib
- Downloads
PostScript 89 KB
PDF 227 KB
BibTeX
- Notes
- The original publication is available at link.springer.com.
- Search for this paper
- Google · Google Scholar
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.