Coupling and self-stabilization |
| |
Authors: | Laurent Fribourg Stéphane Messika laudine Picaronny |
| |
Affiliation: | (1) LSV, CNRS & ENS de Cachan, 61 av. du Prés. Wilson, 94235 Cachan cedex, France |
| |
Abstract: | A randomized self-stabilizing algorithm
is an algorithm that, whatever the initial configuration is, reaches a set
of М legal configurations} in finite time with probability 1. The proof of convergence towards
is generally done by exhibiting a potential function
, which measures the “vertical” distance of any configuration to
, such that
decreases with non-null probability at each step of
. We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance
between any pair of configurations, such that
decreases in expectation at each step of
. In contrast with classical methods, our coupling method does not require the knowledge of
. In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different
measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as
examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs. |
| |
Keywords: | Randomized distributed algorithms Rates of convergence Markov chains Fault tolerance |
本文献已被 SpringerLink 等数据库收录! |
|