Easily rendering token-ring algorithms of distributed and parallel applications fault tolerant

Luciana Arantes 1 Julien Sopena 1
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We propose in this paper a new algorithm that, when called by existing token ring-based algorithms of parallel and distributed applications, easily renders the token tolerant to losses in presence of node crashes. At most k consecutive node crashes are tolerated in the ring. Our algorithm scales very well since a node monitors the liveness of at most k other nodes and neither a global election algorithm nor broadcast primitives are used to regenerate a new token. It is thus very effective in terms of latency cost. Finally, a study of the probability of having at most k consecutive node crashes in the presence of f failures and a discussion of how to extend our algorithm to other logical topologies are also presented.
Type de document :
Rapport
[Research Report] RR-8359, INRIA. 2013, pp.23
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00859863
Contributeur : Julien Sopena <>
Soumis le : lundi 9 septembre 2013 - 15:52:43
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : jeudi 6 avril 2017 - 16:48:19

Fichier

RR-8359.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00859863, version 1

Collections

Citation

Luciana Arantes, Julien Sopena. Easily rendering token-ring algorithms of distributed and parallel applications fault tolerant. [Research Report] RR-8359, INRIA. 2013, pp.23. 〈hal-00859863〉

Partager

Métriques

Consultations de la notice

279

Téléchargements de fichiers

705