Using probabilistic Kleene algebra for protocol verification

We describe pKA, a probabilistic Kleene-style algebra, based on a well known model of probabilistic/demonic computation. Our technical aim is to express probabilistic versions of Cohen’s separation theorems. Separation theorems simplify reasoning about distributed systems, where with purely algebraic reasoning they can reduce complicated interleaving behaviour to “separated” behaviours each of which can be analysed on its own. Until now that has not been possible for probabilistic distributed systems. Algebraic reasoning in general is very robust, and easy to check: thus an algebraic approach to probabilistic distributed systems is attractive because in that “doubly hostile” environment (probability and interleaving) the opportunities for subtle error abound. Especially tricky is the interaction of probability and the demonic or “adversarial” scheduling implied by concurrency. Our case study — based on Rabin’s Mutual exclusion with bounded waiting — is one where just such problems have already occurred: the original presentation was later shown to have subtle flaws. It motivates our interest in algebras, where assumptions relating probability and secrecy are clearly exposed and, in some cases, can be given simple characterisations in spite of their intricacy.15 page(s