Name
Abstract | ||
|---|---|---|
Starting from any configuration, a snap-stabilizing protocol guarantees that the system always behaves according to its specification while a self-stabilizing protocol only guarantees that the system will behave according to its specification in a finite time. So, a snap-stabilizing protocol is a time optimal self-stabilizing protocol (because it stabilizes in 0 rounds). That property is very suitable in the case of systems that are prone to transient faults. There exist a lot of approaches of the concept of self-stabilization, but to our knowledge, snap-stabilization is the only variant of self-stabilization which has been proved power equivalent to self-stabilization in the context of the state model (a locally shared memory model) and for non anonymous systems. So the problem of the existence of snap-stabilizing solutions in the message passing model is a very crucial question from a practical point of view. In this paper, we present the first snap-stabilizing propagation of information with feedback (PIF) protocol for non-oriented trees in the message passing model. Moreover using slow and fast timers, the round complexity of our algorithm is in theta(h x k) and theta((h x k)+k(2)), respectively, where h is the height of the tree and k is the maximal capacity of the channels. We conjecture that our algorithm is optimal. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-11764-5_21 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Topology,Computer science,Communication channel,Self-stabilization,Theoretical computer science,Fault tolerance,Distributed algorithm,State model,Conjecture,Message passing,Finite time | Conference | 8756 |
ISSN | Citations | PageRank |
0302-9743 | 3 | 0.38 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Florence Levé | 1 | 51 | 10.20 |
| Khaled Mohamed | 2 | 3 | 0.72 |
| Vincent Villain | 3 | 544 | 45.77 |