Alessandro Panconesi and Aravind Srinivasan, who received their doctorates from Cornell CS under the supervision of David Shmoys, have been awarded the 2019 Edsger W. Dijkstra Prize in Distributed Computing for their paper “Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds.”
The prize is name in honor of Edsger W. Dijkstra (1930-2002), a Dutch systems analyst and pioneer in distributed computing. Indeed, he has had an outsized impact on research in principles of distributed computing. As the IEEE Computer Society notes: “Among his contributions to computer science is the shortest path-algorithm, also known as Dijkstra’s algorithm; Reverse Polish Notation and related Shunting yard algorithm; the THEmultiprogramming system; Banker’s algorithm; and the semaphore construct for coordinating multiple processors and programs.” They also emphasize that Dijkstra innovated the concept of “self-stabilization,” which is understood as “an alternative way to ensure the reliability of the system.”
The Dijkstra Prize is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributing computing have been evident for at least a decade. The prize is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC).
Computer Science Professor Fred Schneider was awarded the Dijkstra Prize in 2018, and in 2009 Professor Joseph Halpern received the prize (along with Halpern's former student, Yoram Moses).
Panconesi is a professor of computer science in the Department of Information at Sapienza, the University of Rome. Srinivasan is a professor of computer science at the University of Maryland, College Park.
Lastly, here is an account of Panconesi and Srinivasan’s award-winning work:
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.