On the Nature of Progress

Maurice Herlihy

Computer Science Department
Brown University

 We identify a simple relationship that unifies seemingly unrelated
progress conditions ranging from the deadlock-free and starvation-free
properties common to lock-based systems, to non-blocking conditions
such as obstruction-freedom, lock-freedom, and wait-freedom.

Properties can be classified along two dimensions based on the demands
they make on the operating system scheduler. A gap in the
classification reveals a new non-blocking progress condition, weaker
than obstruction-freedom, which we call clash-freedom.

The classification provides an intuitively-appealing explanation why
programmers continue to devise data structures that mix both blocking
and non-blocking progress conditions. It also explains why the
wait-free property is a natural basis for the consensus hierarchy: a
theory of shared-memory computation requires an independent progress
condition, not one that makes demands of the operating system
scheduler.