×

Analysis of a large number of Markov chains competing for transitions. (English) Zbl 1307.93369

Summary: We consider the behaviour 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 analyse the first time at which one of the Markov chains reaches its absorbing state. When the number of Markov chains goes to infinity, we analyse the asymptotic behaviour of the system for an arbitrary probability mass function governing the competition. We give conditions that ensure the existence of the asymptotic distribution and we show how these results apply to cluster-based distributed storage when the competition is handled using a geometric distribution.

MSC:

93E03 Stochastic systems in control theory (general)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
93A14 Decentralized systems

Software:

PEPS
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Anceaume E, Methodology and Computing in Applied Probability (2010)
[2] DOI: 10.1109/32.297942 · Zbl 05114136 · doi:10.1109/32.297942
[3] DOI: 10.1145/278298.278303 · Zbl 1065.68578 · doi:10.1145/278298.278303
[4] Fourneau, J-M. 2008. Discrete Time Markov Chains Competing Over Resources: Product Form Steady-state Distribution. Proceedings of the 5th International Conference on the Quantitative Evaluation of Systems (QEST’08). 2008. pp.147–156. Saint-Malo, France
[5] Luby M, in Proceedings of the IEEE International Symposium on Foundations of Computer Science (FOCS) pp 271– (2002)
[6] Maymounkov P, Research Report TR2002-833 (2002)
[7] Neuts M F, Matrix-geometric Solutions in Stochastic Models: An Algorithmic Approach (1981) · Zbl 0469.60002
[8] Nielsen R, Genetics 158 pp 885– (2001)
[9] Plateau, B, Fourneau, J-M and Lee, K H. 1988. PEPS: A Package for Solving Complex Markov Models of Parallel Systems. Proceedings of the 4th International Conference on Modeling Techniques and Tools for Computer Performance Evaluation Systems. 1988. Majorca, Spain
[10] Shokrollahi A, IEEE/ACM Transactions on Networking 14 pp 2551– (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.