A distributed algorithm for strong bisimulation reduction of state spaces

S.C.C. Blom, S.M. Orzan

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

41 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)74-86
TijdschriftInternational Journal on Software Tools for Technology Transfer
Volume7
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 2005

Vingerafdruk

Duik in de onderzoeksthema's van 'A distributed algorithm for strong bisimulation reduction of state spaces'. Samen vormen ze een unieke vingerafdruk.

Citeer dit