Snap-Stabilizing PIF on Arbitrary Connected Networks in Message Passing Model - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Snap-Stabilizing PIF on Arbitrary Connected Networks in Message Passing Model

(1) , (2) , (1)
1
2

Résumé

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.
Fichier non déposé

Dates et versions

hal-03636481 , version 1 (10-04-2022)

Identifiants

Citer

Florence Levé, Khaled Mohamed, Vincent Villain. Snap-Stabilizing PIF on Arbitrary Connected Networks in Message Passing Model. STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2016, Nov 2016, Lyon, France. pp.281-297, ⟨10.1007/978-3-319-49259-9\_22⟩. ⟨hal-03636481⟩
22 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More