In: Journal of Parallel and Distributed Computing 15. 1992.
Abstract: Stochastic marked graphs are a concurrent decision free formalism provided with a powerful synchronization mechanism generalizing convential fork/join queueing networks. Their exact analysis suffers from the classical state explosion problem. Embedded in the divide and conquer paradigm, this paper introduces a new technique for an iterative analysis. The basic idea leads to the notion of a cut to split the original net system into two parts. On a structural level, we compute the workload of the subnets and preserve their marking behavior. For this purpose the results from qualitative theory of marked graphs are taken into account. From the stochastic perspective, the throughput computation on aggregated subsystems uses a response time approximation. Experimental results on several examples usually have an error of less than 3-5 per cent. The state space is usually reduced by more than one or two orders of magnitude; therefore the analysis of otherwise intractable systems is possible. The generalization of the idea leads to multiple cuts, where single cuts can be applied recursively leading to a hierarchical decomposition (i.e. cuts are at different levels).