Attiya, HagitGuerraoui, RachidHendler, DannyKuznetsov, Petr2009-05-192009-05-192009-05-19200910.1145/1538902.1538908https://infoscience.epfl.ch/handle/20.500.14299/40172WOS:000268486500006Obstruction-free implementations of concurrent ob jects 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 paper, 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 ob ject 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, of step contention. We also show that lock-based implementations are not sub ject to some of the time-complexity lower bounds we present.shared memorysolo-fast implementationsperturbable objectsstep contentionmemory contentionlower boundstext::journal::journal article::research article