The Association for Computing Machinery (ACM) has recognized the work of Michael L. Scott, professor of computer science at the University of Rochester, for the influence his research has had on modern computing. The ACM awarded Scott the 2006 Edsger W. Dijkstra Prize in Distributed Computing for his 1991 paper titled, "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors." Multiprocessors today are used for almost all supercomputing and major corporate and Internet servers.
Scott shares the award with John Mellor-Crummey, co-author of the paper who earned his doctorate from the University of Rochester in 1989. Mellor-Crummey is now associate professor in the Department of Computer Science at Rice University.
"At the time we wrote our paper, conventional wisdom held that synchronization imposed fundamental limits on multiprocessor performance, due to contention for memory and network bandwidth," says Scott. "We were among the first to show that this need not be the case, and the first to clearly articulate the issues in a way that captured widespread attention."
Scott and Mellor-Crummey introduced a new approach to mutual exclusion, a form of synchronization in which processors take turns at some critical task. Their solution, named the MCS lock after their initials, is described by the award committee as "probably the most influential practical mutual exclusion algorithm of all time." The lock is widely used in both commercial and research systems. Scott and Mellor-Crummey also suggested that synchronization algorithms be evaluated in terms of the number of memory accesses that contend with other processors for physical resources. This suggestion has been adopted as a standard metric in the field. More broadly, the paper helped launch the research area known as scalable synchronization.
Scott and Mellor-Crummey's work has gained increasing interest in the last few years as conventional processors have stopped getting faster and the industry is turning toward multiple-processor machines, such as those built from Intel's latest dual-core processors.
"Past recipients of the award are absolute stars of the field. John and I are honored and humbled to be listed with them," says Scott.
The Edsger W. Dijkstra Prize in Distributed Computing is named for Edsger W. Dijsktra, a pioneer in the area of distributed computing. No other individual has had a larger influence on the foundations of the field. The Dijkstra Prize honors a paper "whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade."
The winning authors received plaques and a cash award of $1,000 at a ceremony in Denver, Colo., on July 25.