Brown CS News

Maurice Herlihy Wins Second Edsger W. Dijkstra Prize

Last update on Nov. 18, 2012.

Maurice Herlihy, along with co-author Eliot Moss, was awarded the 2012 ACM-EATCS Edsger W. Dijkstra Prize in Distributed Computing. This Prize is awarded to outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributed computing have been evident for at least ten years.

The 2012 Edsger W. Dijkstra prize was awarded to Maurice Herlihy and Eliot Moss for their paper “Transactional Memory: Architectural Support for Lock-Free Data Structures," and to Nir Shavit and Dan Touitou for their paper “Software Transactional Memory.”

These papers pioneered the idea that concurrent programs should synchronize with one another via transactions, blocks of code that appear to execute atomically. Transactions are easier to use than conventional synchronization methods, and are widely used in databases. Nevertheless, transactions were considered too heavy-weight to support directly either in hardware, or in general-purpose programming languages.

Herlihy’s paper described how modern multiprocessor architectures can support transactions directly in hardware, through simple modifications to standard cache coherence protocols. First published in 1993, this idea was slow to catch on, but in 2012, it was announced that both IBM’s BlueGene/Q supercomputer and Intel’s Haswell processor would provide support for transactional memory in hardware, ensuring that hardware transactional memory is here to stay.

Maurice’s previous Dijkstra Prize was in 2003 for the 1991 article, Wait-Free Synchronization.

Next entry

Previous entry