The Edsger W. Dijkstra Prize in Distributed Computing is awarded for 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.
The 2006 Edsger W. Dijkstra Prize in Distributed Computing goes to
“Algorithms for scalable synchronization on shared-memory multiprocessors”
John M. Mellor-Crummey and Michael L. Scott
ACM Transactions on Computer Systems, 9(1), 1991
Mutual exclusion is one of, if not “the” most studied problem in concurrency control. One of Edsger W. Dijkstra’s most famous contributions to distributed computing was the first working solution to this fundamental problem. In his 1965 paper Dijkstra wrote:
Given in this paper is a solution to a problem which, to the knowledge of the author, has been an open question since at least 1962, irrespective of the solvability. […] Although the setting of the problem might seem somewhat academic at first, the author trusts that anyone familiar with the logical problems that arise in computer coupling will appreciate the significance of the fact that this problem indeed can be solved.
Fast forward to 2006. Mutual exclusion is no longer considered an academic problem. In fact, it forms the basis for almost all concurrent programming and systems, from operating systems to databases to web servers to simulation algorithms.
Mellor-Crummey and Scott’s paper introduced the MCS queue-based mutual exclusion lock: probably the most influential practical mutual exclusion algorithm of all time. The MCS lock is vastly superior to all previous mutual exclusion algorithms (and many proposed since!). It is fast, scalable, and fair in a wide variety of multiprocessor systems, and eliminates serious drawbacks of other algorithms, such as the need to pre-allocate memory for a fixed, predetermined number of threads.
Today this classic algorithm and variations on it are used in numerous systems and applications. For just one illustrative example, the monitor locks used in Java VMs on tens of millions of desktops are variants of MCS. The elegance and wide applicability of MCS have led to it being taught in undergraduate and graduate courses in concurrent programming and operating systems at top institutions around the world. With the growing importance of multi-threaded and multi-core systems today, the influence of the MCS work is especially relevant.
Apart from presenting this algorithm, the awarded paper provides a comprehensive performance comparison against other lock algorithms. It also presents existing and new algorithms for barrier synchronization and similarly provides an in-depth comparison of their performance. The key lesson this work has taught us is that one cannot underestimate the importance of reducing memory traffic in scalable synchronization algorithms. The “local spinning” technique used by the MCS algorithm has heavily influenced virtually all practical scalable synchronization algorithms since.
Dijkstra was right that the mutual exclusion problem was not merely of academic interest, and we are sure that the the work of Mellor-Crummey and Scott will continue to have widespread influence on both academic research and real-world systems work. It is therefore the pleasure of the 2006 Dijkstra Prize Award Committee and the Distributed Computing Community to congratulate them on their achievement.
Dahlia Malkhi (Chair)
Yoram Moses
Michel Raynal
Nir Shavit
July 3rd 2006