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

PDF
Tschaikowski_Max.pdf 1MB 
Abstract
Quantitative analysis by means of discretestate stochastic processes is hindered by the wellknown phenomenon of statespace 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 continuoustime 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 twodimensional 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 largescale mobile models in continuous space like ad hoc networks and multiagent systems.
Item Type:  Thesis (Dissertation, LMU Munich) 

Subjects:  600 Natural sciences and mathematics 600 Natural sciences and mathematics > 510 Mathematics 
Faculties:  Faculty of Mathematics, Computer Science and Statistics 
Language:  English 
Date Accepted:  16. June 2014 
1. Referee:  Tribastone, Mirco 
Persistent Identifier (URN):  urn:nbn:de:bvb:19171109 
MD5 Checksum of the PDFfile:  4a4603ce17da1d58c8241bb2ad3ad788 
Signature of the printed copy:  0001/UMC 22158 
ID Code:  17110 
Deposited On:  07. Jul 2014 08:56 
Last Modified:  20. Jul 2016 10:36 