Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(16)
Complex System
Differential Equation
Exact Solution
Fluid Flow
kolmogorov equation
Large Classes
Model Generation
Performance Modelling
State Space Explosion
Stochastic Calculus
Stochastic Process Algebra
Stochastic Simulation
Higher Order
Markov Model
markovian process algebra
Process Algebra
Related Publications
(1)
Fluid Flow Approximation of PEPA models
Subscribe
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
Edit
A fluid analysis framework for a Markovian process algebra
(
Citations: 15
)
BibTex

RIS

RefWorks
Download
Richard A. Hayden
,
Jeremy T. Bradley
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 fluidflow 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 fluidflow 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 ChapmanKolmogorov 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 fluidfl ow calculation is, in a given modelling situation.
Journal:
Theoretical Computer Science  TCS
, vol. 411, no. 2224, pp. 22602297, 2010
DOI:
10.1016/j.tcs.2010.02.001
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.
(
www.sciencedirect.com
)
(
pubs.doc.ic.ac.uk
)
(
dx.doi.org
)
(
linkinghub.elsevier.com
)
More »
Citation Context
(10)
...Recently, socalled 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 rstorder 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 Stefanek
,
et 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 Massink
,
et al.
Modelling Nonlinear Crowd Dynamics in BioPEPA
...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 Stefanek
,
et 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
References
(45)
Extended Markovian Process Algebra
(
Citations: 58
)
Marco Bernardo
,
Roberto Gorrieri
Conference:
International Conference on Concurrency Theory  CONCUR
, pp. 315330, 1996
Stochastic Concurrent Constraint Programming
(
Citations: 26
)
Luca Bortolussi
Journal:
Electronic Notes in Theoretical Computer Science  ENTCS
, vol. 164, no. 3, pp. 6580, 2006
Coping with the Parallelism of BitTorrent: Conversion of PEPA to ODEs in Dealing with State Space Explosion
(
Citations: 15
)
Adam Duguid
Conference:
Formal Modeling and Analysis of Timed Systems  FORMATS
, pp. 156170, 2006
Hierarchical Markovian Models: Symmetries and Reduction
(
Citations: 47
)
Peter Buchholz
Journal:
Performance Evaluation  PE
, vol. 22, no. 1, pp. 93110, 1995
An Efficient Algorithm for Aggregating PEPA Models
(
Citations: 54
)
Stephen Gilmore
,
Jane Hillston
,
Marina Ribaudo
Journal:
IEEE Transactions on Software Engineering  TSE
, vol. 27, no. 5, pp. 449464, 2001
Sort by:
Citations
(15)
Fluid analysis of energy consumption using rewards in massively parallel markov models
(
Citations: 1
)
Anton Stefanek
,
Richard A. Hayden
,
Jeremy T. Bradley
Published in 2011.
Modelling Nonlinear Crowd Dynamics in BioPEPA
Mieke Massink
,
Diego Latella
,
Andrea Bracciali
,
Jane Hillston
Conference:
Fundamental Approaches to Software Engineering  FASE
, pp. 96110, 2011
Magnetic resonance imaging visualization of a vaginal septum
Georgia Papaioannou
,
Grigorios Koussidis
,
Lina Michala
Journal:
Fertility and Sterility  FERT STERIL
, vol. 96, no. 5, pp. 11931194, 2011
GPA  A Tool for Fluid Scalability Analysis of Massively Parallel Systems
Anton Stefanek
,
Richard A. Hayden
,
Jeremy T. Bradley
Conference:
Quantitative Evaluation of Systems  QEST
, 2011
Approximate Mean Value Analysis of Process Algebra Models
Mirco Tribastone
Conference:
Modeling, Analysis, and Simulation On Computer and Telecommunication Systems  MASCOTS
, pp. 369378, 2011