Anonymity-Preserving Failure Detectors

Abstract : The paper investigates the consensus problem in anonymous, failures prone and asynchronous shared memory systems. It introduces a new class of failure detectors, called anonymity-preserving failures detectors suited to anonymous systems. As its name indicates, a failure detector in this class cannot be relied upon to break anonymity. For example, the anonymous perfect detector AP , which gives at each process an estimation of the number of processes that have failed belongs to this class. The paper then determines the weakest failure detector among this class for consensus. This failure detector, called C, may be seen as a loose failures counter: (1) after a failure occurs, the counter is eventually incremented, and (2) when at least two processes do not fail, it eventually stabilizes. Finally, the paper also introduces failure detector Ck , a simple generalization of C and shows that it can be used to solve k-set-agreement, a generalization of consensus in which up to k distinct values may be decided.
Type de document :
Rapport
[Research Report] LaBRI - Laboratoire Bordelais de Recherche en Informatique. 2016
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01344446
Contributeur : Corentin Travers <>
Soumis le : lundi 11 juillet 2016 - 21:57:04
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17

Fichier

C-fullversion.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01344446, version 1

Collections

Citation

Zohir Bouzid, Corentin Travers. Anonymity-Preserving Failure Detectors. [Research Report] LaBRI - Laboratoire Bordelais de Recherche en Informatique. 2016. 〈hal-01344446〉

Partager

Métriques

Consultations de la notice

111

Téléchargements de fichiers

83