Observing locally self-stabilization

Issue title: Self-Stabilizing Systems, Part 1

Article type: Research Article

Authors: Beauquier, Joffroy | Pilard, Laurence | Rozoy, Brigitte

Affiliations: Université Paris-Sud, Laboratoire de Recherche en Informatique, 91405 Orsay cedex, France E-mail: {beauquier,pilard,rozoy}@lri.fr

Abstract: A self-stabilizing algorithm cannot detect by itself that stabilization has been reached. For overcoming this drawback Lin and Simon introduced the notion of an external observer, i.e., a set of processes, one being located at each node, whose role is to detect stabilization. We propose here a less expensive approach, where there is a single observing process located at a unique node. This process is not allowed to detect false stabilization and it must eventually detect that stabilization is reached. Moreover it must not interfere with the observed self-stabilizing algorithm. Our result is that there exists such an observer for any problem on a distinguished network having a synchronous self-stabilizing solution. Note that our proof is constructive.

Journal: Journal of High Speed Networks, vol. 14, no. 1, pp. 3-19, 2005