Snap-stabilization and PIF in tree networks

摘要

The contribution of this paper is threefold. First, we present the paradigm of snap-stabilization. A snap-stabilizing protocol guarantees that, starting from an arbitrary system configuration, the protocol always behaves according to its specification. So, a snap-stabilizing protocol is a time optimal self-stabilizing protocol (because it stabilizes in 0 rounds). Second, we propose a new Propagation of Information with Feedback (PIF) cycle, called Propagation of Information with Feedback and Cleaning (PFC). We show three different implementations of this new PIF. The first one is a basic PFC cycle which is inherently snap-stabilizing. However, the first PIF cycle can be delayed O(h~2) rounds (where h is the height of the tree) due to some undesirable local states.rnThe second algorithm improves the worst delay of the basic PFC algorithm from O(h~2) to 1 round. The state requirement for the above two algorithms is 3 states per processor, except for the root and leaf processors that use only 2 states. Also, they work on oriented trees. We then propose a third snap-stabilizing PIF algorithm on un-oriented tree networks. The state requirement of the third algorithm depends on the degree of the processors, and the delay is at most h rounds. Next, we analyze the maximum waiting time before a PIF cycle can be initiated whether the PIF cycle is infinitely and sequentially repeated or launch as an isolated PIF cycle. The analysis is made for both oriented and un-oriented trees. We show or conjecture that the two best of the above algorithms produce optimal waiting time. Finally, we compute the minimal number of states the processors require to implement a single PIF cycle, and show that both algorithms for oriented trees are also (in addition to being time optimal) optimal in terms of the number of states.