Paper Info
Title
Snap-Stabilizing PIF on Arbitrary Connected Networks in Message Passing Model.
Abstract
Starting from any configuration, a snap-stabilizing algorithm guarantees that the system always behaves according to its specification while a self-stabilizing algorithm only guarantees that the system will behave according to its specification in a finite time. So, a snap-stabilizing algorithm is a time optimal self-stabilizing algorithm (because it stabilizes in 0 rounds). That means that even the first attempt of using a snap-stabilizing algorithm by any user (human or algorithm) will produce a correct execution. This is a very desirable property, especially in the case of systems that are prone to transient faults. 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. Snap-stabilization has been proven power equivalent to self-stabilization in the state model (a locally shared memory model) and for non-anonymous systems. That result is based on the existence of transformers built from a snap-stabilizing propagation of information with feedback (PIF) algorithm combined with some of its derivatives. In this paper, we present the first snap-stabilizing PIF algorithm for arbitrary connected networks in the message passing model. With a good setting of the timers, the time complexity of our algorithm is in theta(n x k) rounds, where n and k are the number of processors and the maximal channel capacity, respectively. We then conclude that snap-stabilization is power equivalent to self-stabilization in the message passing model with bounded channels for non-anonymous systems.
Year
DOI
Venue
2016
10.1007/978-3-319-49259-9_22
Lecture Notes in Computer Science
Field
DocType
Volume
Computer science,Parallel computing,Message passing,Finite time
Conference
10083
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
15
3
Name
Order
Citations
PageRank
Florence Levé15110.20
Khaled Mohamed230.72
Vincent Villain354445.77