Maurice Herlihy for “Wait-Free Synchronization”, ACM Transactions on Programming Languages and Systems, January 1991, 13(1):124-149.
Members of the selection committee were Yehuda Afek, Michael Merritt, Sergio Rajsbaum (chair), and Sam Toueg. The following descriptions of the winning paper’s contributions were written by Vassos Hadzilacos and Nir Shavit. Vassos Hadzilacos writes the following:
In this paper Herlihy developed a beautiful and useful theory of fault-tolerant computation in distributed systems where asynchronous processes communicate by accessing shared objects of arbitrary types. He showed that objects of different types can differ widely in their ability to support fault-tolerant computations, and defined a hierarchy that classifies objects according to that ability. He also proved the universality of consensus, a fundamental result that facilitates this classification of objects and highlights the central role of the consensus problem in fault-tolerant computing. The paper builds on surprisingly diverse work by other researchers (Lamport and Peterson, who pioneered the notion of wait freedom; Fischer, Lynch and Paterson, who proved the impossibility of consensus in asynchronous message-passing systems and pioneered bivalency proofs; and Loui and Abu Amara, who demonstrated that certain specific strong synchronization primitives can help us solve consensus), but it unifies that work and extends it in truly novel and unexpected ways.
Herlihy’s paper has been extremely influential in shaping the theory of distributed computing. It has also been influential in practice, by providing solid justification for modern multiprocessors to support in hardware universal synchronization primitives such as compare-and-swap rather than weaker primitives such as fetch-and-add.
Nir Shavit writes the following:
This paper laid the structural foundation for the area of multiprocessor synchronization, and introduced two of its most fundamental notions: the Wait-free Hierarchy and the Universality of Consensus. When I try to think of a parallel to Dr. Herlihy’s discoveries in other (albeit broader, arguably more important) scientific fields, the concept that comes to mind is Dimitri Mendeleyev’s discovery of the Periodic Table of the Elements. In a manner similar to Mendeleyev’s choice of Atomic Weight, a property introduced by others, to form a hierarchy among the elements, Herlihy chose the “solvability of consensus,” a property introduced by Fischer, Lynch, and Paterson, as the defining property that forms a hierarchy among wait-free and lock-free concurrent objects. The effect of Dr. Herlihy’s paper on researchers in our specialized field was similar, if not in scale, then in spirit: it introduced structure and order where formerly chaos and intuition reined, and it invigorated numerous scientists to set on a quest to extend the results and fill in the gaps.
The notion of wait-freedom can be attributed to Lamport and others in the 70s and 80s, and was a subject of great interest in the distributed computing community for several years prior to Dr. Herlihy’s presentation of his paper. What was new in “wait-free synchronization” was that it pondered wait-freedom in its most general form: “Given two concurrent objects X and Y, does there exist a wait-free implementation of X by Y?” The paper provided us with many answers, but most importantly with a tool, the solvability of consensus, a tool that helped us fit together the many answers we had, and showed us for the first time how to make use of them in classifying the power of concurrent objects. It also showed us consensus’s power by introducing the notion of the Universality and Universal Constructions, considered by many to be the “Turing machines” of wait-free computation. Last but not least, it is a beautifully written paper, presenting its ideas with just the right combination of formalism and simplicity, so much so that undergraduates can understand most of it after one reading.
This page maintained by Gil Neiger.
Last modified: December 16, 2003