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 award committee has decided to award the 2026 Edsger W. Dijkstra Prize in Distributed Computing to:
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer
for their paper:
Distributed Verification and Hardness of Distributed Approximation
published in the ACM Symposium on Theory of Computing (STOC 2011) and later in the SIAM Journal on Computing (2012).
This paper presented influential new insights on the cost of distributed computation in bandwidth-constrained networks, demonstrating that in the CONGEST model, the Ω̃(√n + D) communication bound is fundamental, impacting a broad family of graph problems.
At the heart of the paper is an elegant reduction framework connecting communication complexity and distributed verification to lower bounds in the CONGEST model. This framework yielded strong lower bounds for both exact and approximate computation, and it demonstrated that verification can be as hard as construction in a distributed setting. The paper applied this new framework to derive over 20 lower bounds, including for problems like minimum spanning tree, shortest path, and minimum cut.
The influence of this work has been significant, inspiring a decade of sustained research extending the framework to new problems and designing algorithms with matching bounds. The techniques introduced in this paper are now standard tools in distributed complexity theory.
Overall, this paper revealed that bandwidth constraints impose a pervasive structural limitation on distributed graph computation, helping to define the modern theory of bandwidth-constrained distributed computing.
2025 Award Committee:
- James Aspnes, Yale University, USA
- Keren Censor-Hillel, Technion, Israel
- Cyril Gavoille, University of Bordeaux, France
- Seth Gilbert, National University of Singapore
- Andrzej Pelc, Universite du Quebec en Outaouais, Canada
- Eric Ruppert, York University, Canada