Exact fluid lumpability for Markovian process algebra

DOI10.1007/978-3-642-32940-1_27MaRDI QIDQ2912691zbMATH OpenOpenAlexWikidataFDO

Authors Max Tschaikowski, Mirco Tribastone

Publication date 25 September 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.4566

zbMATH Keywords

equivalence relationsordinary differential equationsstochastic process algebra

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We consider Markov models of large-scale networks where nodes are characterized by their local behavior and by a mobility model over a two-dimensional lattice. By assuming random walk, we prove convergence to a system of partial differential equations (PDEs) whose size depends neither on the lattice size nor on the population of nodes. This provides a macroscopic view of the model which approximates discrete stochastic movements with continuous deterministic diffusions. We illustrate the practical applicability of this result by modeling a network of mobile nodes with on/off behavior performing file transfers with connectivity to 802.11 access points. By means of an empirical validation against discrete-event simulation we show high quality of the PDE approximation even for low populations and coarse lattices. In addition, we confirm the computational advantage in using the PDE limit over a traditional ordinary differential equation limit where the lattice is modeled discretely, yielding speed-ups of up to two orders of magnitude.

Recommendations

• Exact fluid lumpability in Markovian process algebra
• A unified framework for differential aggregations in Markovian process algebra
• A fluid analysis framework for a Markovian process algebra
• Equivalence and lumpability of FSPNs
• Equivalences for fluid stochastic Petri nets

Cited in

(12)

• A unified framework for differential aggregations in Markovian process algebra
• Logical characterization of fluid equivalences
• Equivalences for fluid stochastic Petri nets
• Comparing chemical reaction networks: a categorical and algorithmic perspective
• Exact fluid lumpability in Markovian process algebra
• Quantitative abstractions for collective adaptive systems
• Differential bisimulation for a Markovian process algebra
• Tackling continuous state-space explosion in a Markovian process algebra
• Symbolic computation of differential equivalences
• Formal lumping of polynomial differential equations through approximate equivalences
• Language-based abstractions for dynamical systems
• Extended differential aggregations in process algebra for performance and biology

This page was built for publication: Exact fluid lumpability for Markovian process algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912691)