Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 16:26:00
Dernière modification le : vendredi 5 août 2022 - 11:22:18




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⟩



Consultations de la notice