Distributed Computation of Transient State Distributions and Passage Time Quantiles in Large Semi-Markov Models

Semi-Markov Processes (SMPs) are expressive tools for modeling parallel and distributed systems; they are a generalization of markov processes that allow for arbitrarily distributed sojourn times. This paper presents an iterative technique for transient and passage time analysis of large structurally unrestricted semi-Markov processes. The authors' method is based on the calculation and subsequent numerical inversion of Laplace transforms and is amenable to a highly scalable distributed implementation. Results for a distributed voting system model with up to 1.1 million states are presented and validated against simulation.