Coupling and Self-Stabilization



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.