Premium
Distributed algorithms in an ergodic Markovian environment
Author(s) -
Comets Francis,
Delarue François,
Schott René
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20154
Subject(s) - ergodic theory , struct , probabilistic logic , ergodicity , limit (mathematics) , reachability , markov process , mathematics , computer science , deadlock , statistical physics , algorithm , pure mathematics , physics , distributed computing , statistics , mathematical analysis , programming language
We provide a probabilistic analysis of the d ‐dimensional banker algorithm when transition probabilities may depend on time and space. The transition probabilities evolve, as time goes by, along the trajectory of an ergodic Markovian environment, whereas the spatial parameter just acts on long runs. Our model complements the one considered by Guillotin‐Plantard and Schott (Random Struct Algorithm 21 (2002) 3–4, 371–396) where transitions are governed by a dynamical system, and appears as a new (small) step towards more general time and space dependent protocols. Our analysis relies on well‐known techniques from stochastic homogenization theory and investigates the asymptotic behavior of the rescaled algorithm as the total amount of resources available for allocation tends to infinity. In the two‐dimensional setting, we manage to exhibit three different possible regimes for the deadlock time of the limit system. To the best of our knowledge, the way we distinguish these regimes is completely new. We interpret our results in terms of stabilization of the algorithm.© 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007