Cumulative measures of absorbing joint Markov chains and an application to Markovian process algebras

Markov Models are of outstanding importance in the performance and reliability evaluation of computer systems and communication networks. In this paper we aim at contributing to the field of Markovian Process Algebras (MPAs). An MPA model is (or may be) the composition of several concurrent sub-components (each of which describes an underlying Markov chain) which may interact with each other through synchronisation. On the one hand the existence of sub-components implies the possibility of the state space explosion problem, i.e. the size of the state space of the Markov chain underlying the composite component grows exponentially in the number of sub-components. On the other hand the interaction of sub-components in general negates the property of independence of their underlying Markov chains, and hence forbids a product-form solution for steady state probabilities. Our target quantities are single steady state probabilities of the Markov chain underlying the composite component. We consider composite components which possess only global synchronisations, i.e. every sub-component is involved in every synchronisation. For this class of MPA models the behaviour of the composite component between two successive synchronisations can be described by the joint process of several absorbing Markov chains. First, a new result on cumulative measures of absorbing joint Markov chains is presented. We compute the mean time to absorption and the mean time the joint Markov chain spends in a certain set before absorption. Our computations do not operate on the state space of the joint Markov chain, and hence the problem of state space explosion is avoided. The computational effort of our method rather depends on convergence properties of the joint Markov chain. Afterwards, this result is applied to compute steady state probabilities for a class of composite components specified as PEPA models which are popular ambassadors of MPAs. It is easily understood that these results carry over from PEPA to other MPA variants.