Professor Aravind Srinivasan receives The 2019 Edsger W. Dijkstra Prize in Distributed Computing

Professor Srinivasan receives the Edsger W. Dijkstra Prize in Distributed Computing for his paper titled "Randomized Distributed Edge Coloring via an Extension of the Chernoff–Hoeffding Bounds", coauthored by Alessandro Panconesi. This paper appeared in the SIAM Journal on Computing in 1997, and an earlier version appeared in PODC 1992.

Several distributed resource-allocation problems, such as contention-free protocols, can be formulated as edge-coloring problems on networks. Prof. Srinivasan’s paper presents the first non-trivial distributed algorithm for this problem, and has led to much activity including improvements and new distributed applications. His paper also presents a concentration-of-measure inequality for sums of "negatively-correlated" random variables, which has since been applied in a large variety of applications.

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. It is named for Edsger Wybe Dijkstra (1930-2002), a pioneer in the area of distributed computing and computer science in general, who was a Turing Award winner. Several well-known computer scientists' papers have won this prize, including Noga Alon, Laszlo Babai, Cynthia Dwork, Joseph Halpern, Leslie Lamport, Nancy Lynch, Mike Paterson, and Michael Rabin.