TU Berlin

Internet Network ArchitecturesAll Publications

Page Content

to Navigation

All publications

On the weakest failure detector for non-blocking atomic commit
Citation key GK-WFDNBAC-02
Author Guerraoui, Rachid and Kouznetsov, Petr
Title of Book International Conference on Theoretical Computer Science (TCS 2002)
Pages 461–473
Year 2002
ISBN 1-4020-7181-7
Location Montreal, Québec, Canada
Volume 223
Month August
Publisher Kluwer
Series IFIP Conference Proceedings
Abstract This paper contributes to the analysis of the Non-Blocking Atomic Commit (NBAC) problem in an asynchronous model with failure detectors. In particular, we address the question of the weakest failure detector to solve NBAC in this model. We define the set A of timeless failure detectors which excludes failure detectors that provide information about global time but includes most known meaningful failure detectors such as ◊S, ◊P and P [2]. We show that, within A, the weakest failure detector for NBAC is ?P+◊S. As a corollary of our results, we state out the relationship between NBAC and another famous agreement problem in distributed computing – Consensus.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe