Department of Computer Science
Department of Computer Science Join Us Department of Computer Science People Department of Computer Science Research Department of Computer Science Academics Department of Computer Science CS Job Board Department of Computer Science About CS Rice Department of Computer Science Events Department of Computer Science CS Home

News

Mellor-Crummey wins 2006 Edsger W. Dijkstra Prize in Distributed Computing

June 29, 2006 - John Mellor-Crummey, associate professor of computer science, and his colleague Michael L. Scott, professor of computer science at the University of Rochester, were awarded the 2006 Edsger W. Dijkstra Prize in Distributed Computing for their 1991 paper, “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.”  Previously known as the Principles of Distributed Computing (PODC) Influential Paper Award, the Dijkstra Prize is awarded to an outstanding paper that has had a proven impact on the theory and practice of distributed computing for at least a decade.

Text from the Symposium on Principles of Distributed Computing proceedings explains the significance of Mellor-Crummey and Scott's work:

"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."

Mellor-Crummey and Scott will receive the Dijkstra Prize of $1,000 at the 25th Annual Association for Computing Machinery (ACM) Symposium on Principles of Distributed Computing, held July 23-26 in Denver. The Dijkstra Prize is the highest recognition given by the distributed systems theory community. The prize is named for Edsger W. Dijsktra, a Dutch computer scientist whose seminal work on concurrency systems, which run simultaneous computations using shared resources, laid groundwork in the area of distributed computing.

Past prize winners were:

2005: Marshal Pease, Robert Shostak, and Leslie Lamport for "Reaching agreement in the presence of faults", Journal of the Association of Computing Machinery, April, 1980, 27(1):228-234.

2004: R. G. Gallager, P. A. Humblet, and P. M. Spira for "A Distributed Algorithm for Minimum-Weight Spanning Trees", ACM Transactions on Programming Languages and Systems, January 1983, 5(1):66-77.

2003: Maurice Herlihy for "Wait-Free Synchronization", ACM Transactions on Programming Languages and Systems, January 1991, 13(1):124-149.

Prizes in the years 2000-2002 were given under the name "PODC Influential-Paper Award".

2002: Edsger W. Dijkstra for "Self-stabilizing systems in spite of distributed control," Communications of the ACM, 1974, 17(11):643-644.

2001: Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson for "Impossibility of Distributed Consensus with One Faulty Process," Journal of the ACM, April 1985, 32(2):374-382.

2000: Leslie Lamport for "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, July 1978, 21(7):558-565.

 


© Copyright 2009  Rice University  
Mailing Address: PO Box 1892, MS-132, Houston TX 77251-1892
Physical Address: 3122 Duncan Hall, 6100 Main Street, Houston TX 77005


Rice University Computer Science