Perfect Failure Detection with Very Few Bits

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
Liste complète des métadonnées

https://hal.inria.fr/hal-01423637
Contributeur : Pierre Fraigniaud <>
Soumis le : vendredi 30 décembre 2016 - 17:52:29
Dernière modification le : vendredi 4 janvier 2019 - 17:33:38

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〉

Partager

Métriques

Consultations de la notice

195