We heard yesterday that Maurice Herlihy's paper on 'wait-free synchronization'is the 2003 winner of the Edsger W. Dijkstra Prize in Distributed Computing. The Edsger W. Dijkstra Prize in Distributed Computing is given to an outstanding paper on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade.
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 type. He showed that objects of different type 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 object and highlights the central role of the consensus problem in fault-tolerant computing.
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.
As winning author, he will receive a cash award of $1,000, and will be presented with a plaque at PODC 2003, where the award will be announced. An announcement of the award recipient will be included in the PODC 2003 proceedings. The announcement will include a paragraph describing the paper's lasting contributions. Congratulations Maurice!
