Dynamic FTSS in asynchronous systems: The case of unison

Swan Dubois 1 Maria Potop-Butucaru 1 Sébastien Tixeuil 2, 3
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient faults hit the system. FTSS (Fault-Tolerant Self-Stabilizing) protocols combine the best of both worlds since they tolerate simultaneously transient and (permanent) crash faults. To date, deterministic FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components.In this paper, we present the first study of deterministic FTSS solutions for dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present several impossibility results for this difficult problem and propose an FTSS solution (when the problem is solvable) for the state model that exhibits optimal fault-containment.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2011, 412 (29), pp.3418-3439. 〈10.1016/j.tcs.2011.02.012〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00627763
Contributeur : Swan Dubois <>
Soumis le : jeudi 29 septembre 2011 - 15:19:28
Dernière modification le : vendredi 25 mai 2018 - 12:02:03

Lien texte intégral

Identifiants

Collections

Citation

Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil. Dynamic FTSS in asynchronous systems: The case of unison. Theoretical Computer Science, Elsevier, 2011, 412 (29), pp.3418-3439. 〈10.1016/j.tcs.2011.02.012〉. 〈inria-00627763〉

Partager

Métriques

Consultations de la notice

162