AGHK-COFI-09

Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov. The Cost of Obstruction-Free Implementations. Journal of the ACM, 56(4):1-33, 2009.

Abstract

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

BibTex Reference

@article{AGHK-COFI-09,
   Author = {Attiya, Hagit and Guerraoui, Rachid and Hendler, Danny and Kuznetsov, Petr},
   Title = {The Cost of Obstruction-Free Implementations},
   Journal = {Journal of the ACM},
   Volume = {56},
   Number = {4},
   Pages = {1--33},
   Year = {2009}
}

EndNote Reference [help]

Get EndNote Reference (.ref)

It has been automatically generated using the bib2html program.