Markov Chains Competing for Transitions: Application to Large-Scale Distributed Systems

Emmanuelle Anceaume 1 François Castella 2, 3 Romaric Ludinard 1 Bruno Sericola 4
1 ADEPT - Algorithms for Dynamic Dependable Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
3 IPSO - Invariant Preserving SOlvers
IRMAR - Institut de Recherche Mathématique de Rennes, Inria Rennes – Bretagne Atlantique
4 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
Abstract : We consider the behavior of a stochastic system composed of several identically distributed, but non independent, discrete-time absorbing Markov chains competing at each instant for a transition. The competition consists in determining at each instant, using a given probability distribution, the only Markov chain allowed to make a transition. We analyze the first time at which one of the Markov chains reaches its absorbing state. We obtain its distribution and its expectation and we propose an algorithm to compute these quantities. We also exhibit the asymptotic behavior of the system when the number of Markov chains goes to infinity. Actually, this problem comes from the analysis of large-scale distributed systems and we show how our results apply to this domain.
Complete list of metadatas

https://hal.inria.fr/inria-00485667
Contributor : Bruno Sericola <>
Submitted on : Tuesday, May 25, 2010 - 4:44:51 PM
Last modification on : Thursday, February 7, 2019 - 5:07:51 PM
Long-term archiving on : Friday, October 19, 2012 - 3:00:09 PM

File

RR-1953.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00485667, version 1

Citation

Emmanuelle Anceaume, François Castella, Romaric Ludinard, Bruno Sericola. Markov Chains Competing for Transitions: Application to Large-Scale Distributed Systems. [Research Report] 2010, pp.29. ⟨inria-00485667⟩

Share

Metrics

Record views

964

Files downloads

263