zbMATH — the first resource for mathematics

Expressing processes with different action durations through probabilities. (English) Zbl 1007.68516
De Alfaro, Luca (ed.) et al., Process algebra and probabilistic methods. Performance modelling and verification. Joint international workshop, PAPM-PROBMIV 2001, Aachen, Germany, September 12-14, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2165, 168-183 (2001).
Summary: We consider a discrete time process algebra capable of (i) modeling processes with different probabilistic advancing speeds (mean number of actions executed per time unit), and (ii) expressing probabilistic external/internal choices and multiway synchronization. We show that, when evaluating steady state based performance measures expressed by associating rewards with actions, such a probabilistic approach provides an exact solution even if advancing speeds are considered not to be probabilistic (i.e. actions of different processes have a different exact duration), without incurring in the state space explosion problem which arises with an intuitive application of a standard synchronous approach. We then present a case study on multi-path routing showing the expressiveness of our calculus and that it makes it particularly easy to produce scalable specifications.
For the entire collection see [Zbl 0971.00028].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q60 Specification and verification (program logics, model checking, etc.)
Full Text: Link