Perfect Failure Detection with Very Few Bits - Equipe Autonomic and Critical Embedded Systems Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2016

Perfect Failure Detection with Very Few Bits

Résumé

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.
Fichier principal
Vignette du fichier
fdenc-longversion.pdf (339.87 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01365304 , version 1 (13-09-2016)

Identifiants

  • HAL Id : hal-01365304 , version 1

Citer

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⟩
164 Consultations
239 Téléchargements

Partager

Gmail Facebook X LinkedIn More