×

zbMATH — the first resource for mathematics

Coping with the parallelism of bittorrent: Conversion of PEPA to ODEs in dealing with state space explosion. (English) Zbl 1141.68503
Asarin, Eugene (ed.) et al., Formal modeling and analysis of timed systems. 4th international conference, FORMATS 2006, Paris, France, September 25–27, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-45026-9/pbk). Lecture Notes in Computer Science 4202, 156-170 (2006).
Summary: The Performance Evaluation Process Algebra (PEPA) language is a stochastic process algebra, generating Continuous Time Markov Chains (CTMC) to allow quantitative analysis. Protocols such as BitTorrent are highly parallel in nature, and represent one area where CTMC analysis is limited by the well-known state space problem. The number of unique states each client can exist in, and the number of clients required to accurately model a typical BitTorrent network preclude the use of CTMCs. Recent work has shown that PEPA models also allow the derivation of an activity matrix, from which ODE and stochastic simulation models, as alternative forms of analysis, are possible. Using this technique, a BitTorrent network is created, analysed, and the results compared against previous BitTorrent models.
For the entire collection see [Zbl 1137.68001].

MSC:
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDF BibTeX XML Cite
Full Text: DOI