direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Selected Publications on Distributed Systems

The Complexity of Obstruction-Free Implementations
Zitatschlüssel AGHK-COFI-09
Autor Attiya, Hagit and Guerraoui, Rachid and Hendler, Danny and Kuznetsov, Petr
Seiten 1–33
Jahr 2009
ISSN 0004-5411
DOI http://dx.doi.org/10.1145/1538902.1538908
Journal Journal of the ACM
Jahrgang 56
Nummer 4
Monat June
Zusammenfassung Obstruction-free implementations of concurrent objects are optimized for the common case where there is no step contention, and were recently advocated as a solution to the costs associated with synchronization without locks. In this article, we study this claim and this goes through precisely defining the notions of obstruction-freedom and step contention. We consider several classes of obstruction-free implementations, present corresponding generic object implementations, and prove lower bounds on their complexity. Viewed collectively, our results establish that the worst-case operation time complexity of obstruction-free implementations is high, even in the absence of step contention. We also show that lock-based implementations are not subject to some of the time-complexity lower bounds we present.
Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe