3532 articles – 5253 Notices  [english version]

hal-00198408, version 1

Large Deviations Analysis for Distributed Algorithms in an Ergodic Markovian Environment

Francis Comets 1, Francois Delarue () 1, René Schott 2, 3

Applied Mathematics and Optimization 60, 3 (2009) 341--396

Résumé : 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.

  • 1 :  Laboratoire de Probabilités et Modèles Aléatoires (LPMA)
  • CNRS : UMR7599 – Université Pierre et Marie Curie [UPMC] - Paris VI – Université Paris VII - Paris Diderot
  • 2 :  Institut Elie Cartan Nancy (IECN)
  • CNRS : UMR7502 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 3 :  TRIO (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • Domaine : Mathématiques/Probabilités
  • Mots-clés : Large deviations – distributed algorithm – averaging principle – Hamilton-Jacobi equation – viscosity solution
 
  • hal-00198408, version 1
  • http://hal.archives-ouvertes.fr/hal-00198408
  • oai:hal.archives-ouvertes.fr:hal-00198408
  • Contributeur : Francois Delarue <>
  • Soumis le : Lundi 17 Décembre 2007, 11:36:53
  • Dernière modification le : Lundi 6 Juin 2011, 13:41:27