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

Abstract

Semi-Markov processes (SMPs) are expressive tools for modelling concurrent systems; they are a generalisation of Markov processes that allow for arbitrarily distributed sojourn times. The paper presents an iterative technique for passage time and transient 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 compared against simulation.