The Edsger W. Dijkstra Prize in Distributed Computing is awarded for 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 a decade. It 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.
The committee decided to award the 2019 Edsger W. Dijkstra Prize in Distributed Computing to
Alessandro Panconesi and Aravind Srinivasan
for their paper
Randomized Distributed Edge Coloring via an Extension of the Chernoff–Hoeffding Bounds, SIAM Journal on Computing, volume 26, number 2, 1997, pages 350–368.
A preliminary version of this paper appeared as “Fast Randomized Algorithms for Distributed Edge Coloring”, Proceedings of the Eleventh Annual ACM Symposium Principles of Distributed Computing (PODC), 1992, pages 251–262.
The paper presents a simple synchronous algorithm in which processes at the nodes of an undirected network color its edges so that the edges adjacent to each node have different colors. It is randomized, using 1.6∆ + O(log1+δ n) colors and O(log n) rounds with high probability for any constant δ > 0, where n is the number of nodes and ∆ is the maximum degree of the nodes. This was the first nontrivial distributed algorithm for the edge coloring problem and has influenced a great deal of follow-up work. Edge coloring has applications to many other problems in distributed computing such as routing, scheduling, contention resolution, and resource allocation.
In spite of its simplicity, the analysis of their edge coloring algorithm is highly nontrivial. Chernoff–Hoeffding bounds, which assume random variables to be independent, cannot be used. Instead, they develop upper bounds for sums of negatively correlated random variables, for example, which arise when sampling without replacement. More generally, they extend Chernoff–Hoeffding bounds to certain random variables they call λ-correlated. This has directly inspired more specialized concentration inequalities. The new techniques they introduced have also been applied to the analyses of important randomized algorithms in a variety of areas including optimization, machine learning, cryptography, streaming, quantum computing, and mechanism design.
Award Committee 2019:
- Lorenzo Alvisi, Cornell University
- Shlomi Dolev, Ben Gurion University
- Faith Ellen (chair), University of Toronto
- Idit Keidar, Technion
- Fabian Kuhn, University of Freiburg
- Jukka Suomela, Aalto University
