Name
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. |
Year | Venue | Keywords |
|---|---|---|
2005 | J. High Speed Networks | central daemon,zero step,fault-tolerance,internal processor,pif,arbitrary un-oriented tree,self-stabilization,self-stabilizing protocol,distributed systems,wave algorithms.,snap-stabilizing propagation,snap-stabilization,snap-stabilizing protocol,snap-stabilizing pif algorithm,arbitrary initial system configuration,extreme end processor,fault tolerant,lower bound,fault tolerance,self stabilization,distributed system |
Field | DocType | Volume |
Upper and lower bounds,Computer science,System configuration,Algorithm,Real-time computing,Self-stabilization,Fault tolerance,Daemon,Distributed computing | Journal | 14 |
Issue | ISSN | Citations |
2 | 0926-6801 | 10 |
PageRank | References | Authors |
0.55 | 18 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alain Cournier | 1 | 281 | 22.07 |
| Ajoy K. Datta | 2 | 369 | 35.83 |
| Franck Petit | 3 | 736 | 60.02 |
| Vincent Villain | 4 | 544 | 45.77 |