A Probabilistic Dynamic Technique for the Distributed Generation of Very Large State Spaces
File(s)
Submitted version
Author(s)
Knottenbelt, W
Harrison, P
Mestern, M
Kritzinger, P
Type
Journal Article
Abstract
Conventional methods for state space exploration are limited to the analysis of small systems because they suffer from excessive memory and computational requirements. We have developed a new dynamic probabilistic state exploration algorithm which addresses this problem for general, structurally unrestricted state spaces.\r\n\r\nOur 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.\r\n\r\nWe derive a performance model of this new algorithm in order to quantify its benefits in terms of distributed run-time, speedup and efficiency. We implement our technique on a distributed-memory parallel computer and demonstrate results which compare favourably with the performance model. Finally, we discuss suitable choices for the three hash functions upon which our algorithm is based.
Version
Submitted version
Date Issued
2000-02
Citation
Performance Evaluation, 2000, 39 (1), pp.127-148
ISSN
0166-5316
Publisher
Elsevier
Start Page
127
End Page
148
Journal / Book Title
Performance Evaluation
Volume
39
Issue
1
Copyright Statement
© 2000 Elsevier Science B.V. All rights reserved. NOTICE: this is the author’s version of a work that was submitted for publication in Performance Evaluation. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in PERFORMANCE EVALUATION, VOL:39, ISSUE:1, (2000) DOI:10.1016/S0166-5316(99)00061-9
Source Volume Number
39