We propose obstruction-free step complexity, a new complexity measure for nonblocking algorithms. We believe that this measure provides a more pragmatic quanti.cation
of nonblocking algorithms than previous measures, providing better guidance for designers of practical nonblocking algorithms.
In our opinion, the main shortcoming of existing complexity measures for nonblocking algorithms is that they are targeted
towardsworst-case behavior inworstcase scenarios, and say little about behavior inmore common cases.This is true for the sensitivity measure of Attiya and Dagan [1], and the d-local step complexity of Afek et al. [2]. These measures are directed at evaluating the behavior of algorithms under contention, i.e., when concurrent
operations actively interfere with each other’s progress. However, in practice, a well-designed system manages contention
so that it does not impact performance too greatly. Thus, these previous measures do not evaluate the behaviour that is likely
to be observed.