Observing locally self-stabilization

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.