AESOP home

Publications

A fluid analysis framework for a Markovian process algebra

Richard Hayden, Jeremy T. Bradley

Journal Article
Theoretical Computer Science
Volume 411
Issues 22–24
pp.2260–2297
May, 2010
Elsevier
DOI 10.1016/j.tcs.2010.02.001
Abstract

Markovian process algebras, such as PEPA and stochastic pi-calculus, bring a powerful compositional approach to the performance modelling of complex systems. However, the models generated by process algebras, as with other interleaving formalisms, are susceptible to the state space explosion problem. Models with only a modest number of process algebra terms can easily generate so many states that they are all but intractable to traditional solution techniques. Previous work aimed at addressing this problem has presented a fluid-flow approximation allowing the analysis of systems which would otherwise be inaccessible. To achieve this, systems of ordinary differential equations describing the fluid flow of the stochastic process algebra model are generated informally.

In this paper, we show formally that for a large class of models, this fluid-flow analysis can be directly derived from the stochastic process algebra model as an approximation to the mean number of component types within the model. The nature of the fluid approximation is derived and characterised by direct comparison with the Chapman-Kolmogorov equations underlying the Markov model. Furthermore, we compare the fluid approximation with the exact solution using stochastic simulation and we are able to demonstrate that it is a very accurate approximation in many cases.

For the first time, we also show how to extend these techniques naturally to generate systems of differential equations approximating higher order moments of model component counts. These are important performance characteristics for estimating, for instance, the variance of the component counts. This is very necessary if we are to understand how precise the fluid-flow calculation is, in a given modelling situation.

Notes

Submitted to TCS, September 2008. Accepted 5 Feb 2010.

PDF of full publication (554.8 kilobytes)
(need help viewing PDF files?)

Information from pubs.doc.ic.ac.uk/fluid-framework-mpa.