TU Berlin

Internet Network ArchitecturesAll Publications


zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

All publications

The Weakest Failure Detectors to Boost Obstruction-Freedom
Zitatschlüssel GKK-WFDBOF-06
Autor Guerraoui, Rachid and Kapalka, Michal and Kouznetsov, Petr
Buchtitel Proceedings of the 20th International Conference on Distributed Computing (DISC '06)
Seiten 399–412
Jahr 2006
ISBN 978-3-540-44624-8
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/11864219_28
Adresse Berlin / Heidelberg, Germany
Jahrgang 4167
Monat September
Verlag Springer
Serie Lecture Notes in Computer Science (LNCS)
Zusammenfassung 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 zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe