AESOP home


Probability, Parallelism and the State Space Exploration Problem

William J. Knottenbelt, Mark Mestern, Peter G. Harrison, Pieter Kritzinger

Conference or Workshop Paper
TOOLS'98, 10th International Conference on Modelling, Techniques and Tools
August, 1998
Lecture Notes in Computer Science
Volume 1469
Springer Verlag

We present a new dynamic probabilistic state exploration algorithm based on hash compaction. Our method has a low state omission probability and low memory usage that is independent of the length of the state vector. In addition, the algorithm can be easily parallelised. This combination of probability and parallelism enables us to rapidly explore state spaces that are an order of magnitude larger than those obtainable using conventional exhaustive techniques. We implement our technique on a distributed-memory parallel computer and we present results showing good speedups and scalability. Finally, we discuss suitable choices for the three hash functions upon which our algorithm is based.

PDF of full publication (638.9 kilobytes)
(need help viewing PDF files?)

Information from