The weakest failure detectors to solve quittable consensus and nonblocking a tomic commit

Rachid Guerraoui; Vassos Hadzilacos; Petr Kuznetsov; Sam Toueg

doi:10.1137/070698877

The weakest failure detectors to solve quittable consensus and nonblocking a tomic commit

Rachid Guerraoui
, Vassos Hadzilacos
, Petr Kuznetsov
, Sam Toueg

Research output: Contribution to journal › Article › peer-review

Abstract

We define quittable consensus, a natural variation of the consensus problem, where processes have the option to agree on "quit" if failures occur, and we relate this problem to the well-known problem of nonblocking atomic commit. We then determine the weakest failure detectors for these two problems in all environments, regardless of the number of faulty processes.

Original language	English
Pages (from-to)	1343-1379
Number of pages	37
Journal	SIAM Journal on Computing
Volume	41
Issue number	6
DOIs	https://doi.org/10.1137/070698877
Publication status	Published - 31 Dec 2012
Externally published	Yes

Keywords

Asynchronous distributed computing
Atomic commit problem
Consensus
Failure detection
Faulttolerant algorithms

Access to Document

10.1137/070698877

Cite this

@article{d86937b5fbe94fcda6256c634915de75,

title = "The weakest failure detectors to solve quittable consensus and nonblocking a tomic commit",

abstract = "We define quittable consensus, a natural variation of the consensus problem, where processes have the option to agree on {"}quit{"} if failures occur, and we relate this problem to the well-known problem of nonblocking atomic commit. We then determine the weakest failure detectors for these two problems in all environments, regardless of the number of faulty processes.",

keywords = "Asynchronous distributed computing, Atomic commit problem, Consensus, Failure detection, Faulttolerant algorithms",

author = "Rachid Guerraoui and Vassos Hadzilacos and Petr Kuznetsov and Sam Toueg",

year = "2012",

month = dec,

day = "31",

doi = "10.1137/070698877",

language = "English",

volume = "41",

pages = "1343--1379",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

number = "6",

}

TY - JOUR

T1 - The weakest failure detectors to solve quittable consensus and nonblocking a tomic commit

AU - Guerraoui, Rachid

AU - Hadzilacos, Vassos

AU - Kuznetsov, Petr

AU - Toueg, Sam

PY - 2012/12/31

Y1 - 2012/12/31

N2 - We define quittable consensus, a natural variation of the consensus problem, where processes have the option to agree on "quit" if failures occur, and we relate this problem to the well-known problem of nonblocking atomic commit. We then determine the weakest failure detectors for these two problems in all environments, regardless of the number of faulty processes.

AB - We define quittable consensus, a natural variation of the consensus problem, where processes have the option to agree on "quit" if failures occur, and we relate this problem to the well-known problem of nonblocking atomic commit. We then determine the weakest failure detectors for these two problems in all environments, regardless of the number of faulty processes.

KW - Asynchronous distributed computing

KW - Atomic commit problem

KW - Consensus

KW - Failure detection

KW - Faulttolerant algorithms

U2 - 10.1137/070698877

DO - 10.1137/070698877

M3 - Article

AN - SCOPUS:84871537245

SN - 0097-5397

VL - 41

SP - 1343

EP - 1379

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

The weakest failure detectors to solve quittable consensus and nonblocking a tomic commit

Abstract

Keywords

Access to Document

Fingerprint

Cite this