Optimal snap-stabilizing PIF algorithms in un-oriented trees

Abstract

A snap-stabilizing protocol, starting from any arbitrary initial system configuration, always behaves according to its specification. In other words, a snap-stabilizing protocol is a self-stabilizing protocol which stabilizes in zero steps. In this paper, we first prove the number of states required on processors to design a snap-stabilizing Propagation of Information with Feedback (PIF) algorithm in arbitrary un-oriented trees running under any distributed daemon (four states per processor for the middle processors and two states for each of the two extreme end processors).

Then, we propose two snap-stabilizing PIF algorithms for un-oriented trees. The former works under any (fair or unfair, central or distributed) daemon. It matches the lower bound in terms of number of states we established in this paper. The latter works under any (fair or unfair) central daemon. It uses only three states for the internal processors (two states for the root and the leaves). It is optimal in terms of number of states assuming a central daemon.

Thus, both algorithms are optimal both in terms of the stabilization time (zero steps) and state requirement per processor.