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 environmentstochastic homogenizationreflected diffusion

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

• 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?)
• A probalistic solution of the Neumann problem.
• Averaging of backward stochastic differential equations, with application to semi-linear pde's
• Large deviations for a Markov chain in a random landscape
• Topics in the Constructive Theory of Countable Markov Chains

Cited in

(8)

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

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)