Large deviations analysis for distributed algorithms in an ergodic Markovian environment
From MaRDI portal
Abstract: We provide a large deviations analysis of deadlock phenomena occurring in distributed systems sharing common resources. In our model transition probabilities of resource allocation and deallocation are time and space dependent. The process is driven by an ergodic Markov chain and is reflected on the boundary of the d-dimensional cube. In the large resource limit, we prove Freidlin-Wentzell estimates, we study the asymptotic of the deadlock time and we show that the quasi-potential is a viscosity solution of a Hamilton-Jacobi equation with a Neumann boundary condition. We give a complete analysis of the colliding 2-stacks problem and show an example where the system has a stable attractor which is a limit cycle.
Recommendations
- Distributed algorithms in an ergodic Markovian environment
- Probabilistic analysis of some distributed algorithms
- scientific article; zbMATH DE number 125893
- Stochastic analysis of average-based distributed algorithms
- Distributed randomized algorithms for probabilistic performance analysis
- Asymptotic Properties of Distributed and Communicating Stochastic Approximation Algorithms
- A theory of distributed Markov chains
- Large deviations and rare events in the study of stochastic algorithms
- Ergodic Randomized Algorithms and Dynamics Over Networks
- Performance of a Distributed Stochastic Approximation Algorithm
Cites work
- scientific article; zbMATH DE number 3826915 (Why is no real title available?)
- scientific article; zbMATH DE number 3972180 (Why is no real title available?)
- scientific article; zbMATH DE number 635661 (Why is no real title available?)
- scientific article; zbMATH DE number 1158743 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- A time-reversed representation for the tail probabilities of stationary reflected Brownian motion.
- An Analysis of a Memory Allocation Scheme for Implementing Stacks
- Colliding stacks: A large deviations analysis
- Distributed algorithms in an ergodic Markovian environment
- Distributed algorithms with dynamical random transitions
- Dynamic random walks on Heisenberg groups
- Hamilton-Jacobi Equations with State Constraints
- Large deviations analysis of reflected diffusions and constrained stochastic approximation algorithms in convex sets†
- Large deviations analysis of some recursive algorithms with state dependent noise
- Large deviations and queueing networks: Methods for rate function identification
- Large deviations and stochastic homogenization
- Large deviations for processes with discontinuous statistics
- Large deviations for stochastic processes.
- M�langes d'�quations diff�rentielles et grands �carts � la loi des grands nombres
- Neumann type boundary conditions for Hamilton-Jacobi equations
- Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
- Probabilistic analysis of some distributed algorithms
- Probability with Martingales
- Random walks, heat equation and distributed algorithms
- Sample path large deviations and convergence parameters
- Some distributed algorithms revisited
- Stochastic differential equations with reflecting boundary conditions
- The Large Deviation Principle for a General Class of Queueing Systems I
- Viscosity solutions of Hamilton-Jacobi equations
Cited in
(7)- Excessive backlog probabilities of two parallel queues
- Stochastic analysis of average-based distributed algorithms
- Approximation of the exit probability of a stable Markov modulated constrained random walk
- Probabilistic analysis of some distributed algorithms
- Distributed algorithms in an ergodic Markovian environment
- Distributed algorithms with dynamical random transitions
- Analysis of distributed systems via quasi-stationary distributions
This page was built for publication: Large deviations analysis for 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 Q843968)
