Academic
Publications
A fluid analysis framework for a Markovian process algebra

A fluid analysis framework for a Markovian process algebra,10.1016/j.tcs.2010.02.001,Theoretical Computer Science,Richard A. Hayden,Jeremy T. Bradley

A fluid analysis framework for a Markovian process algebra   (Citations: 15)
BibTex | RIS | RefWorks Download
Markovian process algebras, such as PEPA and stochastic �-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 susce ptible 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 differe ntial 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 usin g 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 differ- ential 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-fl ow calculation is, in a given modelling situation.
Journal: Theoretical Computer Science - TCS , vol. 411, no. 22-24, pp. 2260-2297, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Recently, so-called uid analysis of performance models [4, 5] makes it possible to analyse systems which exhibit a high degree of parallelism...
    • ...We also have the ability to generate higher moments in the course of such analysis and have a good understanding of when the rst-order analysis produces a good transient approximation to the underlying Markov model [5, 6]. The contribution of this paper is to show, for the rst time, how it is possible to derive reward measures from massive stochastic models using uid analysis techniques...
    • ...To get insight into the variability in the underlying stochastic model, we can also derive the variance and higher moments of these counts [5]...
    • ...For the quantities (E){(S), this problem is addressed in [5] (based on the earlier work in [4]), where a system of ODEs is derived that approximates the temporal evolution of the means and higher and joint moments of the individual counts...
    • ...The main contribution of this work is an extension of the method from [5] that gives ODEs for the quantities (E){ (S)...
    • ...We give an exact form of these ODEs and show how to apply similar approximations to those from [5] to get a system that can be numerically solved alongside the ODEs for moments of component counts...
    • ...Grouped PEPA or GPEPA [5] is a simple syntactic extension of the stochastic process algebra PEPA dened to provide a more elegant treatment of the ODE moment approximation...
    • ...In the context of Grouped PEPA models, it is sucient to represent each state of the underlying CTMC by a numerical vector N(t) consisting of counts NG;P (t) for each possible pair of group label G and component P (as in [5])...
    • ...It has been shown in [5] how to derive approximations to the dierential equations governing the expectations of these counts E[NG;P (t)]...
    • ...For example, if we let Pi(t) to stand for NP;Pi (t) and Ri(t) for NR;Ri (t) for i = 0; 1, the method from [5] gives the approximations e E[] to the exact means E[]:...
    • ...The authors of [5] further extended this method to derive ODE approximations to higher and joint moments of the counts, such as variances, covariances and others...
    • ...The method from [5] provides ODEs with solutions e...
    • ...While massive state space Markov reward analysis is now feasible, one of the recognised features of dierential equation analysis is that it is an approximation of the explicit state space model [5]...

    Anton Stefaneket al. Fluid analysis of energy consumption using rewards in massively parall...

    • ...We provide an alternative analytical explanation for the observed correspondence which is partially based on recent work by Hayden and Bradley [11] on PEPA...
    • ...A third approach, by Hayden and Bradley [11], has recently been applied to assess the quality of the fluid approximation for (grouped) PEPA models...
    • ...6 For a formal definition see for example [11]...
    • ...Let us now consider, following the approach outlined in [11], how an ODE for the function PA(t) can be obtained...
    • ...If at this point, as shown in [11], the functions (1 − c) (X�1) were just constant rates, then expectation would just distribute over multiplication and one would obtain an equation in terms of expectations of populations...

    Mieke Massinket al. Modelling Non-linear Crowd Dynamics in Bio-PEPA

    • ...GPA implements techniques to generate systems of ODEs that approximate means and higher moments of component counts in models described in the Grouped PEPA process algebra by Hayden and Bradley [1]...
    • ...The following section contains a GPA model definition with syntax very similar to the GPEPA formalism [1], describing a simple client/server model [4, 3]:...

    Anton Stefaneket al. GPA - A Tool for Fluid Scalability Analysis of Massively Parallel Syst...

    • ...Lastly, and perhaps most importantly, this validation study offers a comparative evaluation of the accuracy against the competing approximate deterministic solution based on ordinary differential equations (ODEs) [13], [14]...

    Mirco Tribastone. Approximate Mean Value Analysis of Process Algebra Models

    • ...2 Fluid approximation has been applied in particular as an analysis tool for the collective behavior of Stochastic Process Algebra (SPA) based models of large populations of interacting agents [4], [6], [7], [8]...
    • ...In particular, we plan to investigate PEPA models with passive cooperation [9], [8] and models of genetic regulatory networks with threshold activation of genes...

    Luca Bortolussi. Hybrid Limits of Continuous Time Markov Chains

Sort by: