@inproceedings{797db0d4ba1a41faa027c0de9467fe5c,
title = "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.",
keywords = "Failure detectors, Higman{\textquoteright}s lemma, Well-quasi-order",
author = "Pierre Fraigniaud and Sergio Rajsbaum and Corentin Travers and Petr Kuznetsov and Thibault Rieutord",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2016 ; Conference date: 07-11-2016 Through 10-11-2016",
year = "2016",
month = jan,
day = "1",
doi = "10.1007/978-3-319-49259-9\_13",
language = "English",
isbn = "9783319492582",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "154--169",
editor = "Franck Petit and Borzoo Bonakdarpour",
booktitle = "Stabilization, Safety, and Security of Distributed Systems - 18th International Symposium, SSS 2016, Proceedings",
}