Perfect Failure Detection with Very Few Bits

Abstract : A failure detector is a distributed oracle that provides each process with a module that continuously outputs an estimate of which processes in the system have failed. The perfect failure detector provides accurate and eventually complete information about process failures. We show that, in asynchronous failure-prone message-passing systems, perfect failure detection can be achieved by an oracle that outputs at most ⌈log α(n)⌉ + 1 bits per process in n-process systems, where α denotes the inverse-Ackermann function. This result is essentially optimal, as we also show that, in the same environment, no failure detector outputting a constant number of bits per process can achieve perfect failure detection.
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 [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01365304
Contributeur : Corentin Travers <>
Soumis le : mardi 13 septembre 2016 - 12:42:17
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 13:19:21

Fichier

fdenc-longversion.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01365304, version 1

Collections

Citation

Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers, Petr Kuznetsov, Thibault Rieutord. Perfect Failure Detection with Very Few Bits. [Research Report] LaBRI - Laboratoire Bordelais de Recherche en Informatique. 2016. 〈hal-01365304〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

60