Distributed Algorithms in an Ergodic Markovian Environment

Francis Comets (1) , François Delarue (1) , René Schott (2, 3)

1 LPMA - Laboratoire de Probabilités et Modèles Aléatoires
2 IECN - Institut Élie Cartan de Nancy
3 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

We provide a probabilistic analysis of the 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 appears as a new (small) step towards more general time and space dependent protocols. Our analysis relies on well-known results in stochastic homogenization theory and investigates the asymptotic behaviour of the rescaled algorithm as the total amount of resource available for allocation tends to the infinity. In the two dimensional setting, we manage to exhibit three different possible regimes for the deadlock time of the limit system.

Mots clés: distributed algorithms; random environment; stochastic homogenization; reflected diffusion

Domaines: Probabilités [math.PR]

Francis Comets, François Delarue, René Schott. Distributed Algorithms in an Ergodic Markovian Environment. Random Structures and Algorithms, 2007, 30, pp.131-167. ⟨hal-00005841⟩