TU Berlin

Internet Network ArchitecturesAll Publications

Page Content

to Navigation

All publications

The Weakest Failure Detectors to Boost Obstruction-Freedom
Citation key GKK-WFDBOF-06
Author Guerraoui, Rachid and Kapalka, Michal and Kouznetsov, Petr
Title of Book Proceedings of the 20th International Conference on Distributed Computing (DISC '06)
Pages 399–412
Year 2006
ISBN 978-3-540-44624-8
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/11864219_28
Address Berlin / Heidelberg, Germany
Volume 4167
Month September
Publisher Springer
Series Lecture Notes in Computer Science (LNCS)
Abstract This paper determines necessary and sufficient conditions to implement wait-free and non-blocking contention managers in a shared memory system. The necessary conditions hold even when universal objects (like compare-and-swap) or random oracles are available, whereas the sufficient ones assume only registers. We show that failure detector ◊P is the weakest to convert any obstruction-free algorithm into a wait-free one, and Ω*, a new failure detector which we introduce in this paper, and which is strictly weaker than ◊P but strictly stronger than Ω, is the weakest to convert any obstruction-free algorithm into a non-blocking one.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe