## Coupling and Self-Stabilization

### Authors

- Laurent Fribourg, LSV CNRS & ENS Cachan
- Stephane Messika, LSV CNRS & ENS Cachan
- Claudine Picaronny, LSV CNRS & ENS Cachan

### Abstract

A randomized self-stabilizing
algorithm A is an algorithm that, whatever the initial configuration
is, reaches a set L of legal configurations in finite time with
probability 1. The proof of convergence towards L is generally done by
exhibiting a potential function phi, which measures the vertical
distance of any configuration to cal L, such that phi decreases with
non-null probability at each step of A. We propose here a method,
based on the notion of coupling, which makes use of a horizontal
distance d between any pair of configurations, such that d decreases
in expectation at each step of A. In contrast with classical methods,
our coupling method does not require the knowledge of 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.