Reasoning about Probabilistic Parallel Programs

Abstract

The use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. This gain in simplicity, efficiency, and solvability results in a trade-off of the traditional notion of absolute correctness of algorithms for a more quantitative notion: correctness with a probability between 0 and 1. The addition of the notion of parallelism to the already unintuitive idea of randomization makes reasoning about probabilistic parallel programs all the more tortuous and difficult. In this paper we address the problem of specifying and deriving properties of probabilistic parallel programs that either hold deterministically or with probability 1. We present a proof methodology based on existing proof systems for probabilistic algorithms, the theory of the predicate transformer, and the theory of UNITY. Although the proofs of probabilistic programs are slippery at best, we show that such programs can be derived with the same rigor and elegance that we have seen in the derivation of sequential and parallel programs. By applying this methodology to derive probabilistic programs, we hope to develop tools and techniques that would make randomization a useful paradigm in algorithm design. © 1994, ACM. All rights reserved.