A fluid analysis framework for a Markovian process algebra.

*(English)*Zbl 1334.68151Summary: 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.

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.

##### MSC:

68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |

60J99 | Markov processes |

PDF
BibTeX
XML
Cite

\textit{R. A. Hayden} and \textit{J. T. Bradley}, Theor. Comput. Sci. 411, No. 22--24, 2260--2297 (2010; Zbl 1334.68151)

Full Text:
DOI

##### References:

[1] | Hillston, J., () |

[2] | Priami, C., A stochastic \(\pi\)-calculus, The computer journal, 38, 7, 578-589, (1995) |

[3] | Bernardo, M.; Gorrieri, R., Extended Markovian process algebra, (), 315-330 |

[4] | H. Hermanns, Interactive Markov Chains, Ph.D. Thesis, Universität Erlangen-Nürnberg, July 1998. · Zbl 0937.60065 |

[5] | Bortolussi, L., Stochastic concurrent constraint programming, (), 65-80 |

[6] | Duguid, A., Coping with the parallelism of BitTorrent: conversion of PEPA to ODEs in dealing with state space explosion, (), 156-170 · Zbl 1141.68503 |

[7] | Buchholz, P., Hierarchical Markovian models: symmetries and reduction, Performance evaluation, 22, 1, 93-110, (1995) |

[8] | V. Mertsiotakis, Approximate analysis methods for stochastic process algebras, Ph.D. Thesis, Universität Erlangen-Nürnberg, 1998. · Zbl 0924.68084 |

[9] | Harrison, P.G., Turning back time in Markovian process algebra, Theoretical computer science, 290, 1947-1986, (2003) · Zbl 1044.68117 |

[10] | Hillston, J.; Thomas, N., Product form solution for a class of PEPA models, Performance evaluation, 35, 3-4, 171-192, (1999) · Zbl 1052.68638 |

[11] | Boucherie, R.J., A characterization of independence for competing Markov chains with applications to stochastic Petri nets, IEEE transactions on software engineering, 20, 7, 536-544, (1994) |

[12] | Buchholz, P., Exact and ordinary lumpability in finite Markov chains, Journal of applied probability, 31, 59-75, (1994) · Zbl 0796.60073 |

[13] | Siegle, M., Using structured modelling for efficient performance prediction of parallel systems, (), 453-460 |

[14] | Chiola, G., Manual and automatic exploitation of symmetries in SPN models, (), 28-43 |

[15] | Gilmore, S.T.; Hillston, J.; Ribaudo, M., An efficient algorithm for aggregating PEPA models, IEEE transactions on software engineering, 27, May, 449-464, (2001) |

[16] | Hillston, J., Fluid flow approximation of PEPA models, (), 33-42 |

[17] | Gillespie, D.T., Exact stochastic simulation of coupled chemical reactions, Journal of physical chemistry, 81, 25, 2340-2361, (1977) |

[18] | Bradley, J.T.; Gilmore, S.T.; Hillston, J., Analysing distributed Internet worm attacks using continuous state-space approximation of process algebra models, Journal of computer and system sciences, 74, September, 1013-1032, (2008) · Zbl 1154.68318 |

[19] | Bortolussi, L.; Policriti, A., Stochastic concurrent constraint programming and differential equations, (), 27-42 · Zbl 1279.92031 |

[20] | L. Bortolussi, On the approximation of stochastic concurrent constraint programming by master equation, in: QAPL’08, 6th Workshop on Quantitative Aspects of Programming Languages, Budapest, March 2008. · Zbl 1286.68344 |

[21] | Hoare, C.A.R., Communicating sequential processes, Communications of the ACM, 21, August, 666-677, (1978) · Zbl 0383.68028 |

[22] | Cardelli, L., From processes to ODEs by chemistry, () |

[23] | Cardelli, L., On process rate semantics, Theoretical computer science, 391, February, 190-215, (2008) · Zbl 1133.68054 |

[24] | Cardelli, L., A process algebra master equation, () |

[25] | Geisweiller, N.; Hillston, J.; Stenico, M., Relating continuous and discrete PEPA models of signalling pathways, Theoretical computer science, 404, November, 97-111, (2008) · Zbl 1151.68038 |

[26] | Kurtz, T., Solutions of ordinary differential equations as limits of pure jump Markov processes, Applied probability, 7, April, 49-58, (1970) · Zbl 0191.47301 |

[27] | Le Boudec, J.-Y.; McDonald, D.; Mundinger, J., A generic Mean field convergence result for systems of interacting objects, (), 3-18 |

[28] | Benaïm, M.; Le Boudec, J.-Y., A class of Mean field interaction models for computer and communication systems, Performance evaluation, 65, 11-12, 823-838, (2008) |

[29] | Horton, G.; Kulkarni, V.G.; Nicol, D.M.; Trivedi, K.S., Fluid stochastic Petri nets: theory, applications, and solution techniques, European journal of operational research, 105, 1, 184-201, (1998) · Zbl 0957.90011 |

[30] | Boxma, O.J.; Dumas, V., The busy period in the fluid queue, ACM SIGMETRICS performance evaluation review, 26, 1, 100-110, (1998) |

[31] | Field, A.J.; Harrison, P.G., An approximate compositional approach to the analysis of fluid queue networks, Performance evaluation, 64, September, 1137-1152, (2007) |

[32] | Whitt, W., () |

[33] | Bowman, H.; Bryans, J.W.; Derrick, J., Analysis of a multimedia stream using stochastic process algebras, The computer journal, 44, 4, 230-245, (2001) · Zbl 0993.68068 |

[34] | Fourneau, J.-M.; Kloul, L.; Valois, F., Performance modelling of hierarchical cellular networks using PEPA, Performance evaluation, 50, November, 83-99, (2002) |

[35] | Thomas, N.; Bradley, J.T.; Knottenbelt, W.J., Stochastic analysis of scheduling strategies in a GRID-based resource model, IEE software engineering, 151, September, 232-239, (2004) |

[36] | Holton, D.R.W., A PEPA specification of an industrial production cell, The computer journal, 38, 7, 542-551, (1995) |

[37] | Bradley, J.T.; Dingle, N.J.; Gilmore, S.T.; Knottenbelt, W.J., Derivation of passage-time densities in PEPA models using ipc: the imperial PEPA compiler, (), 344-351 |

[38] | Kemeny, J.G.; Snell, J.L., Finite Markov chains, (1960), Van Nostrand · Zbl 0112.09802 |

[39] | R.A. Hayden, J.T. Bradley, Fluid semantics for passive stochastic process algebra cooperation, in: VALUETOOLS’08, Third International Conference on Performance Evaluation Methodologies and Tools, Athens, 2008. |

[40] | Tribastone, M., The PEPA plug-in project, (), 53-54 |

[41] | Bradley, J.T.; Knottenbelt, W.J., The ipc/HYDRA tool chain for the analysis of PEPA models, (), 334-335 |

[42] | Deavours, D.D.; Clark, G.; Courtney, T.; Daly, D.; Derisavi, S.; Doyle, J.M.; Sanders, W.H.; Webster, P.G., The Möbius framework and its implementation, IEEE transactions on software engineering, 28, October, 956-969, (2002) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.