Passage time distributions in large markov chains

Probability distributions of response times are important in the de-sign and analysis of transaction processing systems and computer-communication systems. We present a general technique for deriv-ing such distributions from high-level modelling formalisms whose state spaces can be mapped onto finite Markov chains. We use a load-balanced, distributed implementation to find the Laplace transform of the first passage time density and its derivatives at arbitrary values of the transform parameter . Setting yields moments while the full passage time distribution is obtained using a novel distributed Laplace transform inverter based on the Laguerre method. We validate our method against a variety of simple densi-ties, cycle time densities in certain overtake-free (tree-like) queue-ing networks and a simulated Petri net model. Our implementation is thereby rigorously validated and has already been applied to sub-stantial Markov chains with over 1 million states. Corresponding theoretical results for semi-Markov chains are also presented. 1