# Perfect Failure Detection with Very Few Bits

2 GANG - Networks, Graphs and Algorithms
IRIF - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : A \emph{failure detector} is a distributed oracle that provides the processes with information about failures. The \emph{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 $\lceil \log \alpha(n)\rceil+1$ bits per process in $n$-process systems, where $\alpha$ denotes the inverse-Ackermann function. This result is essentially optimal, as we also show that, in the same environment, no failure detectors outputting a constant number of bit per process can achieve perfect failure detection.
Type de document :
Communication dans un congrès
18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) , 2016, Lyon, France
Domaine :

https://hal.inria.fr/hal-01423637
Contributeur : Pierre Fraigniaud <>
Soumis le : vendredi 30 décembre 2016 - 17:52:29
Dernière modification le : jeudi 15 novembre 2018 - 20:27:45

### Identifiants

• HAL Id : hal-01423637, version 1

### Citation

Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers, Petr Kuznetsov, Thibault Rieutord. Perfect Failure Detection with Very Few Bits. 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) , 2016, Lyon, France. 〈hal-01423637〉

### Métriques

Consultations de la notice