Snap-stabilization and PIF in tree networks |
| |
Authors: | Alain Bui Ajoy K Datta Franck Petit Vincent Villain |
| |
Affiliation: | (1) CReSTIC, Université de Reims Champagne-Ardenne, Reims, France;(2) School of Computer Science, University of Nevada, Las Vegas, USA;(3) LaRIA CNRS, Université de Picardie Jules Verne, Amiens, France |
| |
Abstract: | 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 ( ). We show three different implementations of this new PIF. The first one is a basic 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. The second algorithm improves the worst delay of the basic
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.
WARNING: The concept of snap-stabilization was first introduced in 12]. The concept evolved over the last eight years. We
take this evolution in consideration in this paper, which includes the early results published in 10] and 12]. In particular,
infinite repetition of computation cycles is a requirement of self-stabilizing systems. This is not required in snap-stabilization because snap-stabilization ensures that the first completed computation cycle is executed according to the
specification of the problem. The correctness proofs conform to this basic property. |
| |
Keywords: | Fault-tolerance Optimality Self-stabilization Snap-stabilization Wave algorithms |
本文献已被 SpringerLink 等数据库收录! |
|