Fluid aggregations for Markovian process algebra

Tschaikowski, Max (2014): Fluid aggregations for Markovian process algebra. Dissertation, LMU München: Faculty of Mathematics, Computer Science and Statistics

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 objects in the model. 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. However, in the modelling of massively distributed computer systems, even aggregated chains may be still too large for efficient numerical analysis. Recently this problem has been addressed by fluid techniques, where the Markov chain is approximated by a system of ordinary differential equations (ODEs) whose size does not depend on the number of the objects in the model. The technique has been primarily applied in the case of massively replicated sequential processes with small local state space sizes. This thesis devises two different approaches that broaden the scope of applicability of efficient fluid approximations. Fluid lumpability applies in the case where objects are composites of simple objects, and aggregates the potentially massive, naively constructed ODE system into one whose size is independent from the number of composites in the model. Similarly to quasi and near lumpability, we introduce approximate fluid lumpability that covers ODE systems which can be aggregated after a small perturbation in the parameters. The technique of spatial aggregation, instead, applies to models whose objects perform a random walk on a two-dimensional lattice. Specifically, it is shown that the underlying ODE system, whose size is proportional to the number of the regions, converges to a system of partial differential equations of constant size as the number of regions goes to infinity. This allows for an efficient analysis of large-scale mobile models in continuous space like ad hoc networks and multi-agent systems.

• Item Type: Theses (Dissertation, LMU Munich)
• Subjects: 500 Natural sciences and mathematics; 500 Natural sciences and mathematics > 510 Mathematics
• Faculties: Faculty of Mathematics, Computer Science and Statistics
• Language: English
• Date of oral examination: 16. June 2014
• 1. Referee: Tribastone, Mirco
• Signature of the printed copy: 0001/UMC 22158