Name
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 ($$\mathcal{PFC}$$). We show three different implementations of this new PIF. The first one is a basic $$\mathcal{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. The second algorithm improves the worst delay of the basic
$$\mathcal{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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00446-007-0030-4 | Distributed computing |
Keywords | Field | DocType |
Fault-tolerance,Optimality,Self-stabilization,Snap-stabilization,Wave algorithms | Topology,Computer science,System configuration,Petroleum engineering,Algorithm,Self-stabilization,Fault tolerance,Conjecture | Journal |
Volume | Issue | ISSN |
20 | 1 | 0178-2770 |
Citations | PageRank | References |
36 | 1.28 | 25 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alain Bui | 1 | 163 | 16.51 |
| Ajoy Kumar Datta | 2 | 317 | 40.76 |
| Franck Petit | 3 | 736 | 60.02 |
| Vincent Villain | 4 | 544 | 45.77 |