Alumni Gazette

‘Distributing’ the Honors

A Rochester alumnus and a University faculty member have teamed up to win a highly regarded computer science prize.

John Mellor-Crummey ’89 (PhD), an associate professor of computer science at Rice University, and Michael Scott, a professor of computer science at Rochester, shared the 2006 Edsger W. Dijkstra Prize in Distributed Computing, one of the top honors from the Association for Computing Machinery.

The two, who did not begin their formal collaboration until after Mellor-Crummey graduated, are credited as the first to describe how microprocessors could share their workload more efficiently if they were forced, in effect, to take turns.

Their ideas, articulated in the 1991 paper “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors,” ran counter to the then conventional wisdom that coordinating operations of multiple processors would require expensive memory and network bandwidth.

Called the “MCS Lock” after the initials of the two scientists, the algorithm and the approaches that followed from it have been widely used in both commercial and research systems.

More broadly, their paper—and a series of later work—helped launch the field known as “scalable synchronization.”

The Dijkstra Prize is presented annually to recognize “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 two scientists first met and became friends while Mellor-Crummey was a graduate student in computer science. But they did not work together until Mellor-Crummey took a research position at Rice.