Quantitative analysis by means of discrete-state stochastic processes is hindered by the well-known phenomenon of state-space explosion, whereby the size of the state space may have an exponential growth with the number of agents of the system under scrutiny. When the stochastic process underlies a Markovian process algebra model, this problem may be alleviated by suitable notions of behavioural equivalence that induce lumping at the underlying continuous-time Markov chain, establishing an exact relation between a potentially much smaller aggregated chain and the original one. For the analysis of massively parallel systems, however, lumping techniques may not be sufficient to yield a computationally tractable problem. Recently, much work has been directed towards forms of fluid techniques that provide a set of ordinary differential equations (ODEs) approximating the expected path of the stochastic process. Unfortunately, even fluid models of realistic systems may be too large for feasible analysis. This paper studies a behavioural relation for process algebra with fluid semantics, called projected label equivalence, which is shown to yield an exactly fluid lumpable model, i.e., an aggregated ODE system which can be related to the original one without any loss of information. Project label equivalence relates sequential components of a process term. In general, for any two sequential components that are related in the fluid sense, nothing can be said about their relationship from the stochastic viewpoint. We define and study a notion of well-posedness which allows us to relate fluid lumpability to the stochastic notion of semi-isomorphism, which is a weaker version of the common notion of isomorphism between the doubly labelled transition systems at the basis of the Markovian interpretation. (C) 2013 Elsevier B.V. All rights reserved.
Exact fluid lumpability in Markovian process algebra
Tribastone M
2014-01-01
Abstract
Quantitative analysis by means of discrete-state stochastic processes is hindered by the well-known phenomenon of state-space explosion, whereby the size of the state space may have an exponential growth with the number of agents of the system under scrutiny. When the stochastic process underlies a Markovian process algebra model, this problem may be alleviated by suitable notions of behavioural equivalence that induce lumping at the underlying continuous-time Markov chain, establishing an exact relation between a potentially much smaller aggregated chain and the original one. For the analysis of massively parallel systems, however, lumping techniques may not be sufficient to yield a computationally tractable problem. Recently, much work has been directed towards forms of fluid techniques that provide a set of ordinary differential equations (ODEs) approximating the expected path of the stochastic process. Unfortunately, even fluid models of realistic systems may be too large for feasible analysis. This paper studies a behavioural relation for process algebra with fluid semantics, called projected label equivalence, which is shown to yield an exactly fluid lumpable model, i.e., an aggregated ODE system which can be related to the original one without any loss of information. Project label equivalence relates sequential components of a process term. In general, for any two sequential components that are related in the fluid sense, nothing can be said about their relationship from the stochastic viewpoint. We define and study a notion of well-posedness which allows us to relate fluid lumpability to the stochastic notion of semi-isomorphism, which is a weaker version of the common notion of isomorphism between the doubly labelled transition systems at the basis of the Markovian interpretation. (C) 2013 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.