The Dijkstra Prize Committee has decided to grant the 2016 Edsger W. Dijkstra Prize in Distributed Computing jointly to Noga Alon, László Babai, Alon Itai, and Michael Luby for the following two papers:
- A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem by Noga Alon, László Babai, and Alon Itai, published in Journal of Algorithms, 7(4):567-583, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set Problem by Michael Luby, published in the Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 1-10, May 1985, and in SIAM Journal on Computing, 15(4):1036-1053, 1986
The Prize is awarded 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.
In these seminal works, the authors present, simultaneously and independently, an O(log n) time randomized distributed/parallel algorithm for the Maximal Independent Set (MIS) problem. MIS is regarded as a crown jewel of distributed symmetry breaking problems, and a central problem in the area of locality in distributed computing. The nominated papers provide a fascinatingly simple, elegant, and efficient randomized solution for this problem. While many variations exist, at their core, the algorithms are as simple as this:
Repeat until done: each node picks an O(log n)-bit random number; strict local minima join the MIS, and get removed from the graph along with their neighbors.
The algorithm has played a significant role in popularizing Distributed Computing to the broader Computer Science community. It is one of the most well-known distributed algorithms, and perhaps the one covered most frequently in general algorithms courses and textbooks, especially those on randomized algorithms.
The algorithm leads to O(log n) time randomized distributed/parallel algorithms for many other basic symmetry breaking problems such as (∆ + 1)-coloring, Maximal Matching, and Ruling Sets. The awarded papers were among the pioneers in demonstrating the striking power of randomization in Distributed Computing, and have received more than 1,000 citations. Interestingly, they were also among the first in observing the simple yet powerful fact that one can derandomize parallel/centralized algorithms that use only d-wise independent randomness for constant d. This fact is used in the papers to derive deterministic parallel MIS algorithms, and it is now viewed as one of the basic derandomization techniques.
Thanks to its simplicity, the algorithm and its variations have been in widespread use, in various settings, from wireless networks to biological systems where symmetry breaking is required. This algorithmic result has also given rise to a host of fundamental and rich theoretical questions. Although to this day many of the questions remain open and continue intriguing the researchers, the follow up work on these questions has advanced our understanding of locality considerably.
The E.W. Dijkstra Prize is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). The prize is presented annually, with the presentation taking place alternately at PODC and DISC. This year it will be presented at PODC to be held at Chicago, IL, USA, July 25-29, 2016.
The 2016 Dijkstra Prize Committee:
- Shlomi Dolev, Ben-Gurion University of the Negev
- Pierre Fraigniaud, CNRS and University Paris Diderot
- Cyril Gavoille, University of Bordeaux (Chair)
- Dahlia Malkhi, VMware Research
- Andrzej Pelc, Université du Québec en Outaouais
- David Peleg, Weizmann Institute