State-optimal snap-stabilizing PIF in tree networks

Introduces the notion of snap stabilization. A snap-stabilizing algorithm protocol guarantees that, starting from an arbitrary system configuration, the protocol always behaves according to its specification. So, a snap-stabilizing protocol is a self-stabilizing protocol which stabilizes in zero steps. We propose a snap-stabilizing PIF (propagation of information with feedback) scheme on a rooted tree network. We call this scheme “Propagation of Information with Feedback and Cleaning” (𝒫ℱ𝒞). We present two algorithms. One is a basic 𝒫ℱ𝒞 scheme which is inherently snap-stabilizing. However, it can be delayed by O(h²) steps (where h is the height of the tree) due to some undesirable local states. The second algorithm improves the worst delay of the basic 𝒫ℱ𝒞 algorithm from O(h²) to one step. 𝒫ℱ𝒞 can be used to implement distributed resetting, distributed infimum computation and a global synchronizer in O(1) waves. Assuming that a checking mechanism exists to detect transient failures or topological changes, 𝒫ℱ𝒞 allows processors to detect if the system is stabilized in O(1) waves without using any global metric. Finally, we show that the state requirement for both 𝒫ℱ𝒞 algorithms matches the exact lower bound of the PIF algorithms on tree networks-three states per processor, except for the root and leaf processors which use only two states. Thus, the proposed algorithms are optimal PIF schemes in terms of the number of states