AESOP home


Exploiting Quasi-reversible Structures in Markovian Process Algebra Models

Peter G. Harrison, Jane Hillston

Journal Article
The Computer Journal
Volume 38
Issue 7
Oxford University Press
DOI 10.1093/comjnl/38.7.510

Efficient product form solution is one of the major attractions of queueing networks for performance modelling purposes. These models rely on a form of interaction between nodes in a network which allows them to be solved in isolation, since they behave as if independent up to normalisation. Markovian process algebras (MPA) extend classical process algebras with information about the duration of actions but retain their compositional structure: a system is modelled as an interaction of components. The advantages of this compositional structure for model construction and model simplification have already been demonstrated. In this paper we exploit results from queueing networks to identify a restricted form of interaction between suitable MPA components which leads to a product form solution. Each component of the model may be solved separately and the compositional structure of an MPA consequently facilitates efficient solution for successively more complex models. This work uses the notion of quasi-reversibility in a Markov process setting to define the type of interaction between MPA components. This leads to a substantial class of MPA definitions that have product-form solutions which is more general than the usual queueing network-based class of Markov processes.

PDF of full publication (5.7 megabytes)
(need help viewing PDF files?)

Information from