Distributed algorithms in an ergodic Markovian environment

DOI10.1002/RSA.20154MaRDI QIDQ3419617zbMATH OpenOpenAlexFDO

Authors Francis Comets, François Delarue, R. Schott

Publication date 7 February 2007

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0507115

zbMATH Keywords

distributed algorithmsrandom environmentreflected diffusionstochastic homogenization

Mathematics Subject Classification ID

Generalizations of martingales (60G48) Processes in random environments (60K37) Distributed algorithms (68W15)

Abstract: 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.

Recommendations

• Large deviations analysis for distributed algorithms in an ergodic Markovian environment
• scientific article; zbMATH DE number 2006656
• scientific article; zbMATH DE number 125893
• Probabilistic analysis of some distributed algorithms
• Probabilistic analysis of a network resource allocation algorithm

Cites work

• A probalistic solution of the Neumann problem.
• Averaging of backward stochastic differential equations, with application to semi-linear pde's
• scientific article; zbMATH DE number 3972180 (Why is no real title available?)
• scientific article; zbMATH DE number 3664138 (Why is no real title available?)
• scientific article; zbMATH DE number 1969513 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• Large deviations for a Markov chain in a random landscape
• Topics in the Constructive Theory of Countable Markov Chains

Cited in

(9)

• Excessive backlog probabilities of two parallel queues
• Analysis of distributed systems via quasi-stationary distributions
• Approximation of excessive backlog probabilities of two tandem queues
• Distributed algorithms with dynamical random transitions
• Distributed Averaging Via Lifted Markov Chains
• Stochastic analysis of average-based distributed algorithms
• Hitting time of a corner for a reflected diffusion in the square
• Hitting probabilities of constrained random walks representing tandem networks
• Large deviations analysis for distributed algorithms in an ergodic Markovian environment

This page was built for publication: Distributed algorithms in an ergodic Markovian environment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3419617)