The Weakest Failure Detectors To Solve Quittable Consensus And Nonblocking Atomic Commit

Guerraoui, Rachid; Hadzilacos, Vassos; Kuznetsov, Petr; Toueg, Sam

doi:10.1137/070698877

The Weakest Failure Detectors To Solve Quittable Consensus And Nonblocking Atomic Commit

Guerraoui, Rachid ; Hadzilacos, Vassos ; Kuznetsov, Petr ; Toueg, Sam

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.

Published in:

Siam Journal On Computing, 41, 6, 1343-1379

Year:

2012

Publisher:

Philadelphia, Society for Industrial and Applied Mathematics

ISSN:

0097-5397

Keywords:

asynchronous distributed computing ; atomic commit problem ; consensus ; fault-tolerant algorithms ; failure detection

DOI:

10.1137/070698877