Tackling continuous state-space explosion in a Markovian process algebra

Fluid or mean-field methods are approximate analytical techniques which have proven effective in tackling the infamous state-space explosion problem which typically arises when modelling large-scale concurrent systems based on interleaving semantics. These methods are particularly suitable in situations which present large populations of simple interacting objects characterised by small local state spaces, since they require the analysis of a problem which is insensitive to the population sizes but is dependent only on the size of the local state spaces. This paper studies the case when the replicated objects are best described as composites which consist of smaller simple objects. A congenial formal modelling framework for situations of this kind may be given by stochastic process algebra. Using PEPA as a representative case, we find that fluid models with replicated copies of composite processes do not scale well with increasing population sizes, thus rendering intractable the analysis of the underlying system of ordinary differential equations (ODEs). We call this problem continuous state-space explosion, by analogy with its counterpart phenomenon in discrete state spaces. The main contribution of this paper is a result of equivalence that simplifies, in an exact way, the potentially massive ODE system arising in those circumstances to one whose size is independent from all the multiplicities in the model. As a byproduct, we find that these simplified ODEs turn out to characterise the fluid behaviour of a family of PEPA models whose elements cannot be related to each other through any known equivalence relation. A substantial numerical assessment investigates the relationship between the different underlying Markov chains and their unique fluid limit, demonstrating its generally good accuracy for all practical purposes. (C) 2013 Elsevier B.V. All rights reserved.