The weakest failure detectors to solve certain fundamental problems in distributed computing

Carole Delporte-Gallet; Vassos Hadzilacos; Hugues Fauconnier; Petr Kouznetsov; Rachid Guerraoui; Sam Toueg

doi:10.1145/1011767.1011818

The weakest failure detectors to solve certain fundamental problems in distributed computing

Carole Delporte-Gallet
, Vassos Hadzilacos
, Hugues Fauconnier
, Petr Kouznetsov
, Rachid Guerraoui
, Sam Toueg

Research output: Contribution to conference › Paper › peer-review

Abstract

We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.

Original language	English
Pages	338-346
Number of pages	9
DOIs	https://doi.org/10.1145/1011767.1011818
Publication status	Published - 1 Jan 2004
Externally published	Yes
Event	Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing - St. John's, Nfld., Canada Duration: 25 Jul 2004 → 28 Jul 2004

Conference

Conference	Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing
Country/Territory	Canada
City	St. John's, Nfld.
Period	25/07/04 → 28/07/04

Keywords

Consensus
Non-blocking atomic commit
Quittable consensus
Register
Weakest failure detector

Access to Document

10.1145/1011767.1011818

Cite this

Delporte-Gallet, C., Hadzilacos, V., Fauconnier, H., Kouznetsov, P., Guerraoui, R., & Toueg, S. (2004). The weakest failure detectors to solve certain fundamental problems in distributed computing. 338-346. Paper presented at Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Nfld., Canada. https://doi.org/10.1145/1011767.1011818

@conference{d7979e7accd345b186b3b069907fb85c,

title = "The weakest failure detectors to solve certain fundamental problems in distributed computing",

abstract = "We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.",

keywords = "Consensus, Non-blocking atomic commit, Quittable consensus, Register, Weakest failure detector",

author = "Carole Delporte-Gallet and Vassos Hadzilacos and Hugues Fauconnier and Petr Kouznetsov and Rachid Guerraoui and Sam Toueg",

year = "2004",

month = jan,

day = "1",

doi = "10.1145/1011767.1011818",

language = "English",

pages = "338--346",

note = "Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing ; Conference date: 25-07-2004 Through 28-07-2004",

}

Delporte-Gallet, C, Hadzilacos, V, Fauconnier, H, Kouznetsov, P, Guerraoui, R & Toueg, S 2004, 'The weakest failure detectors to solve certain fundamental problems in distributed computing', Paper presented at Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Nfld., Canada, 25/07/04 - 28/07/04 pp. 338-346. https://doi.org/10.1145/1011767.1011818

The weakest failure detectors to solve certain fundamental problems in distributed computing. / Delporte-Gallet, Carole; Hadzilacos, Vassos; Fauconnier, Hugues et al.
2004. 338-346 Paper presented at Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, St. John's, Nfld., Canada.

Research output: Contribution to conference › Paper › peer-review

TY - CONF

T1 - The weakest failure detectors to solve certain fundamental problems in distributed computing

AU - Delporte-Gallet, Carole

AU - Hadzilacos, Vassos

AU - Fauconnier, Hugues

AU - Kouznetsov, Petr

AU - Guerraoui, Rachid

AU - Toueg, Sam

PY - 2004/1/1

Y1 - 2004/1/1

N2 - We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.

AB - We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.

KW - Consensus

KW - Non-blocking atomic commit

KW - Quittable consensus

KW - Register

KW - Weakest failure detector

U2 - 10.1145/1011767.1011818

DO - 10.1145/1011767.1011818

M3 - Paper

AN - SCOPUS:10444236388

SP - 338

EP - 346

T2 - Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing

Y2 - 25 July 2004 through 28 July 2004

ER -

The weakest failure detectors to solve certain fundamental problems in distributed computing

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this