An Inductive Technique for Parameterised Model Checking of Degenerative Distributed Randomised Protocols

AbstractWe present a technique to tackle the parameterised probabilistic model checking problem for a particular class of randomised distributed systems, which we model as Markov Decision Processes. These systems, termed degenerative, have the property that a model of a system with some communication graph will eventually behave like a model of a system with a reduced graph. We describe an induction schema for reasoning about models of a degenerative system over arbitrary graphs. We thereby show that a certain class of quantitative LTL properties will hold for a model of a system with any communication graph if it holds for all models of a system with some base graph. We demonstrate our technique via a case study (a randomised leader election protocol) specified using the PRISM modelling language