A fluid analysis framework for a Markovian process algebra
File(s)fluid-framework-mpa.pdf (554.86 KB)
Accepted version
Author(s)
Hayden, RA
Bradley, JT
Type
Journal Article
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.\r\n\r\nIn 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.\r\n \r\nFor 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.
Date Issued
2010-05
Citation
Theoretical Computer Science, 2010, 411 (22-24), pp.2260-2297
ISSN
0304-3975
Publisher
Elsevier
Start Page
2260
End Page
2297
Journal / Book Title
Theoretical Computer Science
Volume
411
Issue
22-24
Copyright Statement
© 2010 Elsevier B.V. All rights reserved. NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in THEORETICAL COMPUTER SCIENCE, VOL:411, ISSUE:22-24, (2010) DOI: 10.1016/j.tcs.2010.02.001
Identifier
http://pubs.doc.ic.ac.uk/fluid-framework-mpa/
Source Volume Number
411
Publication Status
Published