We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Coupling and self-stabilization.
- Authors
Fribourg, Laurent; Messika, Stéphane; Picaronny, laudine
- Abstract
A randomized self-stabilizing algorithm $${\cal A}$$ is an algorithm that, whatever the initial configuration is, reaches a set $${\cal L}$$ of М legal configurations} in finite time with probability 1. The proof of convergence towards $${\cal L}$$ is generally done by exhibiting a potential function $$\varphi$$ , which measures the “vertical” distance of any configuration to $${\cal L}$$ , such that $$\varphi$$ decreases with non-null probability at each step of $${\cal A}$$ . We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance $$\delta$$ between any pair of configurations, such that $$\delta$$ decreases in expectation at each step of $${\cal A}$$ . In contrast with classical methods, our coupling method does not require the knowledge of $${\cal L}$$ . 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.
- Subjects
SELF-stabilization (Computer science); COMPUTER algorithms; FAULT-tolerant computing; ALGORITHMS; ALGEBRA; FOUNDATIONS of arithmetic; CONFIGURATIONS (Geometry); STOCHASTIC convergence; SPIN-spin interactions
- Publication
Distributed Computing, 2006, Vol 18, Issue 3, p221
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-005-0142-7