TU Berlin

Internet Network ArchitecturesDistributed Systems: Selected Publications


zur Navigation

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



Schnellnavigation zur Seite über Nummerneingabe