Distributed computation of transient state distributions and passage time quantiles in large semi-Markov models

Semi-Markov processes (SMPs) are expressive tools for modelling parallel and distributed systems; they are a generalisation 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. Our 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.