Dynamic FTSS in Asynchronous Systems: the Case of Unison

Swan Dubois 1, 2, * Maria Potop-Butucaru 2, 1, * Sébastien Tixeuil 2, *
* Auteur correspondant
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
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 fault hit the system. FTSS protocols combine the best of both worlds since they are simultaneously fault-tolerant and self-stabilizing. To date, 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 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 many impossibility results for this difficult problem and propose a FTSS solution when the problem is solvable that exhibits optimal fault containment.
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00379904
Contributeur : Maria Potop-Butucaru <>
Soumis le : jeudi 10 février 2011 - 15:40:59
Dernière modification le : mardi 17 avril 2018 - 11:28:09
Document(s) archivé(s) le : mercredi 11 mai 2011 - 03:13:53

Fichiers

DuboisPotopTixeuil.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00379904, version 2
  • ARXIV : 0904.4615

Collections

Citation

Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil. Dynamic FTSS in Asynchronous Systems: the Case of Unison. [Research Report] 2009, pp.34. 〈inria-00379904v2〉

Partager

Métriques

Consultations de la notice

362

Téléchargements de fichiers

181