Title: On the Nature of Progress

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 talk will identifies a simple relationship that unifies 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.

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. These assumptions lead to an interesting new classification system for progress properties, one that explains for the first time several previously troubling assumptions and programming practices.

Joint work with Maurice Herlihy.

This document was translated from L^AT_EX by H^EV^EA.