A set of concurrent processes sharing a data object form a fault-tolerant system only if nonfaulty processes can complete their operations in a finite number of steps even if the system contains arbitrarily slow, including halted, processes provided that, except for sharing the object, these slow processes are independent of the nonfaulty processes. An implementation of a data object that guarantees this is called wait-free. Wait-free implementations have a clear advantage, which has led to considerable interest in such implementations of objects.

This paper develops a proof technique for statements of the form “X cannot provide a wait-free implementation of Y.” This technique is then used to derive a hierarchy of objects such that no object can provide a wait-free implementation of any object at a higher level. Herlihy goes on to show that several classical synchronization primitives are unable to provide wait-free implementations of all sequential objects shared by a finite set of processes, but that objects do exist that can.

Considering its length, the paper is elegant, thorough, and well-motivated throughout. It is also highly self-contained in the sense that any computer scientist should be able to read it without needing to dig up a multi-link chain of prior references to get the background. As such, I commend this paper as a model for anyone contemplating writing a paper with more than one theorem in it: considering the wide acceptance of programming disciplines such as top-down refinement in our field, it is amazing how many technical papers insist on throwing theorem after theorem at the reader without once pausing to suggest a plausible reason for doing so; in contrast, the technical content of this paper follows naturally from the discussion in which it is embedded.