Large Deviations Analysis for Distributed Algorithms in an Ergodic Markovian Environment - Université Pierre et Marie Curie Accéder directement au contenu
Article Dans Une Revue Applied Mathematics and Optimization Année : 2009

Large Deviations Analysis for Distributed Algorithms in an Ergodic Markovian Environment

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.
Fichier principal
Vignette du fichier
CDSdec07.pdf (617.74 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00198408 , version 1 (17-12-2007)

Identifiants

Citer

Francis Comets, François Delarue, René Schott. Large Deviations Analysis for Distributed Algorithms in an Ergodic Markovian Environment. Applied Mathematics and Optimization, 2009, 60 (3), pp.341--396. ⟨10.1007/s00245-009-9079-8⟩. ⟨hal-00198408⟩
439 Consultations
178 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More