Communications of the ACM
Two Papers Selected to Receive 2022 Dijkstra Prizes
The 2022 Dijkstra Prize Award Committee is happy to announce that the 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
and
"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.
have been selected to receive this year's Dijkstra Prize, which will be officially awarded at the ACM Symposium on Principles of Distributed Computing (PODC 2022) in July.
Nonblocking concurrent data structures are central to the theory and practice of parallel programming. In principle, they can be used to tolerate thread failures. In practice, they provide immunity from performance anomalies when threads are rotated out of action by the underlying scheduler. They are also immune to priority inversion, and can safely be used in signal handlers, without the need to turn off signals during critical sections. Unfortunately, correct nonblocking structures are difficult to write. A key challenge is to ensure, before reclaiming an unlinked node, that no still-active operation retains a reference to that node.
Hazard Pointers, also known as the "Pass the Buck'' solution to the Repeat Offenders Problem, were the first general-purpose solution to the memory management problem in nonblocking concurrent data structures. They remain the dominant solution today. By maintaining a global set of references to objects (nodes) to which active threads hold private references, they enable nonblocking code to determine when a node can safely be reclaimed. By organizing the set as a collection of per-thread structures, each of which is accessed primarily by its owner, they avoid most nonlocal references, keeping overhead low enough for all but the most demanding applications.
Together, the winning papers revolutionized both the theory and practice of nonblocking algorithms. They have inspired dozens of follow-on projects and (including their brief announcement and journal versions) well over 1,000 citations. Today, hazard pointers are used in an enormous variety of commercial libraries and systems, making them essential to most of the world's datacenters and multicore devices. More, perhaps, than any other single innovation, they have enabled nonblocking concurrent data structures to become a central technology of modern parallel systems.
The Edsger W. Dijkstra Prize in Distributed Computing is named for Edsger Wybe Dijkstra (1930-2002), a pioneer in the area of distributed computing. His foundational work on concurrency primitives (such as the semaphore), concurrency problems (such as mutual exclusion and deadlock), reasoning about concurrent systems, and self-stabilization comprises one of the most important supports upon which the field of distributed computing is built. The prize is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing have been evident for at least a decade. The Prize includes an award of $2,000.
The Prize is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the European Association for Theoretical Computer Science (EATCS) Symposium on Distributed Computing (DISC).
The Award Committee 2022:
Christian Scheideler, Paderborn University (chair)
Marcos Aguilera, VMware Research
Alessandro Panconesi, Università La Sapienza, Rome
Andrea Richa, Arizona State University
Alexander Schwarzmann, Augusta University
Philipp Woelfel, University of Calgary
No entries found