Brown CS News

Every year, the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC) award the Edsger W. Dijkstra Prize in Distributed Computing to distinguished papers that have significantly impacted distributed computing's theory or practice. In 2022, Professor Maurice Herlihy of Brown CS and his collaborators have won the award, the Head of the Dijkstra Prize Committee writes, "for providing the first general approach to memory reclamation in nonblocking data structures, with significant impact both in research and practice".

This is the third time that Maurice has won the Dijkstra Prize, and he's believed to be one of only two people in the award's 23-year history who have received it three times. This time, the Prize Committee recognized two papers:

• “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes,” by Maged M. Michael. Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), Monterey, CA, USA, July 2002, pages 21–30.
• “The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures,” by Maurice Herlihy, Victor Luchangco, and Mark Moir. Proceedings of the 16th International Symposium on Distributed Computing (DISC), Toulouse, France, October 2002, pages 339–353.

In the former, the author (concurrently and independently from the work of Maurice and his collaborators) develops a lock-free memory management method for dynamic lock-free objects that allows arbitrary memory reuse and doesn't require special operating
system or hardware support.

In the latter, Maurice and his coauthors define an abstract problem – the Repeat Offender Problem (ROP) – such that any solution to this problem can be used by dynamic-sized lock-free data structure implementations to allow them to free unused memory with standard memory allocators. They pay particular attention to formulating their problem to support one or more “worker” threads that do most of the work of memory management. This allows us them to separate the scheduling of this work from that of the application and use “spare” processors to do memory management work. They also present the first solution to the ROP problem, which they call “Pass The Buck”.  In a separate report, they show how to apply ROP solutions to achieve the first truly dynamic-sized lock-free data structures and evaluate their performance.

Last year's winner of the Dijkstra Prize was also a member of the Brown CS community, alum Scott Smolka.

For more information, click the link that follows to contact Brown CS Communication and Outreach Specialist Jesse C. Polhemus.