A fluid analysis framework for a Markovian process algebra
A fluid analysis framework for a Markovian process algebra
复制标题
DOI：
10.1016/j.tcs.2010.02.001
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
R. A. Hayden;J. Bradley
中科院分区：
文献类型：
--
作者：
R. A. Hayden;J. Bradley
马尔可夫过程代数，如PEPA和随机π-演算，带来了一个强大的组合方法的复杂系统的性能建模。然而，进程代数生成的模型，与其他交织形式主义，容易受到状态空间爆炸问题。只有少量过程代数项的模型可以很容易地生成如此多的状态，以至于传统的求解技术几乎难以处理。以前的工作，旨在解决这个问题，提出了一个流体流动近似允许系统的分析，否则将无法访问。为了实现这一点，系统的常微分方程描述的随机过程代数模型的流体流动产生非正式的。在本文中，我们正式表明，对于一个大类的模型，这种流体流动分析可以直接从随机过程代数模型作为一个近似的平均数模型内的组件类型。流体近似的性质推导和特点是直接比较与查普曼-柯尔莫哥洛夫方程的马尔可夫模型。此外，我们比较了流体近似的精确解使用随机模拟，我们能够证明，这是一个非常准确的近似在许多情况下。对于第一次，我们还展示了如何扩展这些技术自然生成系统的微分方程近似模型组件计数的高阶矩。这些都是用于估计组件计数方差等重要性能特征。这是非常必要的，如果我们要了解流体流动计算是多么精确，在给定的建模情况。
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 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.