This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ciardo, G. Articles by Nicol, D. Search for Related Content

Distributed State Space Generation of Discrete-State Stochastic Models

Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795
Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795
Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795

High-level formalisms such as stochastic Petri nets can be used to model complex systems. Analysis of logical and numerical properties of these models often requires the generation and storage of the entire underlying state space. This imposes practical limitations on the types of systems that can be modeled. Because of the vast amount of memory consumed, we investigate distributed algorithms for the generation of state space graphs. The distributed construction allows us to take advantage of the combined memory readily available on a network of workstations. The key technical problem is to find effective methods for on-the-fly partitioning, so that the state space is evenly distributed among processors. In this article we report on the implementation of a distributed state space generator that may be linked to a number of existing system modeling tools. We discuss partitioning strategies in the context of Petri net models, and report on performance observed on a network of workstations, as well as on a distributed memory multicomputer.

Key words: Probability; Markov processes; networks; graphs; heuristics

This article has been cited by other articles:

				S. Blom, B. Lisser, J. Van De Pol, and M. Weber A Database Approach to Distributed State-Space Generation J Logic Computation, March 5, 2009; (2009) exp004v1. [Abstract] [PDF]