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

Emmanuelle Anceaume; François Castella; Romaric Ludinard; Bruno Sericola

inria-00485667, version 1

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

Emmanuelle Anceaume ()^a^, 1, François Castella ()^b^, 2, 3, Romaric Ludinard ()^c^, 1, Bruno Sericola ()^c^, 4

(2010)

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.

a – CNRS
b – Université de Rennes I
c – INRIA
1: ADEPT (INRIA - IRISA)
CNRS : UMR6074 – INRIA – Université de Rennes 1
2: Institut de Recherche Mathématique de Rennes (IRMAR)
CNRS : UMR6625 – Université de Rennes 1 – École normale supérieure de Cachan - ENS Cachan – Institut National des Sciences Appliquées (INSA) : - RENNES – Université de Rennes II - Haute Bretagne
3: IPSO (INRIA - IRMAR)
CNRS : UMR6074 – INRIA – Université de Rennes 1
4: DIONYSOS (INRIA - IRISA)
INRIA – Université de Rennes 1 – CNRS : UMR6074

inria-00485667, version 1
http://hal.inria.fr/inria-00485667
oai:hal.inria.fr:inria-00485667
From: Bruno Sericola <>
Submitted on: Tuesday, 25 May 2010 16:44:51
Updated on: Wednesday, 26 January 2011 10:20:06

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

%F inria-00485667, version 1
%0 Report
%U http://hal.inria.fr/inria-00485667
%2 INFO:INFO_MO;INFO:INFO_PF;INFO:INFO_RO
%T Markov Chains Competing for Transitions: Application to Large-Scale Distributed Systems
%A Anceaume, Emmanuelle
%A Castella, François
%A Ludinard, Romaric
%A Sericola, Bruno
%+ ADEPT - INRIA - IRISA , Institut de Recherche Mathématique de Rennes - IRMAR , IPSO - INRIA - IRMAR , DIONYSOS - INRIA - IRISA
%X 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.
%2 Nous considérons un systéme stochastique composé de plusieurs chaînes de Markov à temps discret, absorbantes, identiques mais non indépendantes, et en compétition à chaque instant pour une transition. La compétition consiste à déterminer à chaque instant la seule chaîne de Markov autorisée à faire une transition. On analyse le premier instant auquel une des chaînes de Markov est absorbée. On obtient sa distribution et sa moyenne et l'on propose un algorithme pour calculer ces quantités. On exhibe de plus le comportement asympotique du système quand le nombre de chaînes de Markov tend vers l'infini. En fait, ce problème vient de l'analyse des systèmes distribués grande échelle et l'on montre comment nos résultats s'appliquent à ce domaine.
%G English
%2 Research Report
%P 29
%8 2010-05-21
%K Markov Chains;Competing Markov Chains;Asymptotic Analysis; Large-Scale Distributed Systems

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00485667"><monogr>
<author><persName><forename>Emmanuelle</forename><surname>Anceaume</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">ADEPT</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>François</forename><surname>Castella</surname></persName>
<affiliation>
<orgName type="laboratory">IRMAR</orgName>
<orgName type="team">Institut de Recherche Mathématique de Rennes</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6625</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
<orgName type="institution">École normale supérieure de Cachan - ENS Cachan</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) : - RENNES</orgName>
<orgName type="institution">Université de Rennes II - Haute Bretagne</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA - IRMAR</orgName>
<orgName type="team">IPSO</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Romaric</forename><surname>Ludinard</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">ADEPT</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Bruno</forename><surname>Sericola</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">DIONYSOS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
<orgName type="institution">CNRS : UMR6074</orgName>
</affiliation>
</author>
<title type="main" level="m">Markov Chains Competing for Transitions: Application to Large-Scale Distributed Systems</title><title type="main" level="m">Markov Chains Competing for Transitions: Application to Large-Scale Distributed Systems</title><imprint><biblScope type="publicationDate">2010-05-21</biblScope><biblScope type="pp">29</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00485667</idno><idno type="HALFile">http://hal.inria.fr/inria-00485667/PDF/RR-1953.pdf</idno></biblStruct>
</listBibl>
</listBibl>