TU Berlin

Internet Network ArchitecturesMarco Canini's Publications


zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Marco Caninis's Publications

The Weakest Failure Detectors to Boost Obstruction-Freedom
Zitatschlüssel GKK-WFDBOF-08
Autor Guerraoui, Rachid and Kapalka, Michal and Kouznetsov, Petr
Seiten 415–433
Jahr 2008
ISSN 0178-2770
DOI http://dx.doi.org/10.1007/s00446-007-0046-9
Adresse Berlin / Heidelberg, Germany
Journal Distributed Computing Journal (DC)
Jahrgang 20
Nummer 6
Verlag Springer
Zusammenfassung It is considered good practice in concurrent computing to devise shared object implementations that ensure a minimal obstruction-free progress property and delegate the task of boosting liveness to independent generic oracles called contention managers. This paper determines necessary and sufficient conditions to implement wait-free and non-blocking contention managers, i.e., contention managers that ensure wait-freedom (resp. non-blockingness) of any associated obstruction-free object implementation. The necessary conditions hold even when universal objects (like compare-and-swap) or random oracles are available in the implementation of the contention manager. On the other hand, the sufficient conditions assume only basic read/write objects, i.e., 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. We also address the issue of minimizing the overhead imposed by contention management in low contention scenarios. We propose two intermittent failure detectors I_Ω^* and I_◊P that are in a precise sense equivalent to, respectively, Ω^* and ◊P, but allow for reducing the cost of failure detection in eventually synchronous systems when there is little contention. We present two contention managers: a non-blocking one and a wait-free one, that use, respectively, I_Ω^* and I_◊P. When there is no contention, the first induces very little overhead whereas the second induces some non-trivial overhead. We show that wait-free contention managers, unlike their non-blocking counterparts, impose an inherent non-trivial overhead even in contention-free executions.
Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe