Back to Search
Start Over
A distributed algorithm for strong bisimulation reduction of state spaces.
- Source :
- International Journal on Software Tools for Technology Transfer; Feb2005, Vol. 7 Issue 1, p74-86, 13p
- Publication Year :
- 2005
-
Abstract
- It is a known problem that state spaces can grow very large, which makes operating on them (including reducing them) difficult because of operational memory shortage. In an attempt to extend the size of the state spaces that can be dealt with, we designed and implemented a bisimulation reduction algorithm for distributed memory settings using message passing communication. By using message passing, the same implementation can be used on both clusters of workstations and large shared memory machines. The algorithm performs reduction of large labeled transition systems modulo strong bisimulation. We justify its correctness and termination and provide an evaluation of the worst-case time and message complexity and some performance data from a prototype implementation. Both theory and practice show that the algorithm scales up with the number of workstations. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
COMPUTERS
PROTOTYPES
COMPUTER programming
RESEARCH
MEMORY
Subjects
Details
- Language :
- English
- ISSN :
- 14332779
- Volume :
- 7
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- International Journal on Software Tools for Technology Transfer
- Publication Type :
- Academic Journal
- Accession number :
- 15909493
- Full Text :
- https://doi.org/10.1007/s10009-004-0159-4