Large Deviations Analysis for Distributed Algorithms in an Ergodic Markovian Environment

被引：0
作者：
Francis Comets
François Delarue
René Schott
机构：
[1] Université Paris 7,Laboratoire de Probabilités et Modèles Aléatoires
[2] UFR de Mathématiques,IECN and LORIA
[3] Université Henri Poincaré-Nancy 1,undefined
来源：
Applied Mathematics and Optimization | 2009年 / 60卷
关键词：
Large deviations; Distributed algorithm; Averaging principle; Hamilton-Jacobi equation; Viscosity solution;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：341 / 396
页数：55
相关论文
共 32 条
  • [1] Atar R.(1999)Large deviations and queueing networks: methods for rate function identification Stoch. Process. Appl. 84 255-296
  • [2] Dupuis P.(1977)Mélanges d’équations différentielles et grands écarts à la loi des grands nombres Z. Wahrscheinlichkeitstheor. Verw. Geb. 38 1-54
  • [3] Azencott R.(1988)Large deviations and stochastic homogenization Ann. Mat. Pura Appl. 151 161-177
  • [4] Ruget G.(1990)Hamilton-Jacobi equations with state constraints Trans. Am. Math. Soc. 318 643-683
  • [5] Baldi P.(2007)Distributed algorithms in an ergodic Markovian environment Random Struct. Algorithms 30 131-167
  • [6] Capuzzo-Dolcetta I.(1987)Large deviations analysis of reflected diffusions and constrained stochastic approximation algorithms in convex sets Stochastics 21 63-96
  • [7] Lions P.-L.(1988)Large deviations analysis of some recursive algorithms with state dependent noise Ann. Probab. 16 1509-1536
  • [8] Comets F.(1995)The large deviations principle for a general class of queueing systems I Trans. Am. Math. Soc. 347 2689-2751
  • [9] Delarue F.(2002)A time-reversed representation for the tail probabilities of stationary reflected Brownian motion Stoch. Process. Appl. 98 253-287
  • [10] Schott R.(2002)Distributed algorithms with dynamic random transitions Random Struct. Algorithms 21 371-396
1234