Abstract:

It is well known that programmers of shared-memory multiprocessor
machines devise both blocking and non-blocking data structures for
the same problem. Moreover, they mix blocking and non-blocking
methods within the same data structure or application. To this date,
there has been no attempt to explain how these seemingly unrelated
progress conditions can actually co-exist in the same real-world
application.

This lecture will survey progress conditions
and identifiy a simple relationship that unifies
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.

Contrary to the prior literature, we will claim that on multiprocessors
progress properties are not about the progress guarantees a method's
implementation provides. Rather, they are about the assumptions one
needs to make on the operating system scheduler so that a method's
implementation behaves as if it were wait-free.

As we will show, properties can be classified along two dimensions based
on the demands they make on the operating system scheduler. By
examining a gap in this table, we discover a new non-blocking
progress condition, weaker than obstruction-freedom, which we call
clash-freedom. Moreover, the classification explains for the first
time why the wait-free and lock-free properties are the most natural
basis for a shared memory consensus hierarchy.

Joint work with Maurice Herlihy of Brown.