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 2025 Edsger W. Dijkstra Prize in Distributed
Computing to

Moni Naor and Larry Stockmeyer (1948–2004)

for their paper:

“What Can Be Computed Locally?”
SIAM Journal on Computing, volume 24, issue 6, pages 1259–1277, 1995
Proc. of the 25th Annual ACM Symp. on Theory of Computing (STOC), 1993

This is arguably one of the most influential papers in the area of distributed graph algorithms; it is the foundation on which our modern understanding of distributed computational complexity and especially locality of graph problems is largely built. While a lot of early work on distributed graph algorithms and locality studied specific individual problems, Naor and Stockmeyer took the first step towards systematically studying distributed computational complexity of entire problem families. To this end, the paper defines the family of locally checkable labeling problems (LCLs). The family of LCLs as defined by Naor and Stockmeyer is broad enough to capture many distributed graph problems of interest, but it is also narrow enough so that it is possible to prove strong theorems that apply to all LCL problems.

In their paper, Naor and Stockmeyer initiated the study of what distributed complexity classes exist for LCL problems. In particular, they showed that there are nontrivial LCL problems with constant locality. They also initiated the the systematic study of meta-computational questions in this area. Further, the paper introduced the use of Ramsey-type arguments in the context of distributed algorithms, and it initiated the study of the role of randomness in distributed graph algorithms.

The work of Naor and Stockmeyer started a research program that is still very actively being pursued today, 30 years later. This is a paper that is deeply influencing what is happening in our research community, and its impact is rapidly finding its way to also other communities, including at least quantum information theory, measurable combinatorics, stochastic processes, neural networks, and game theory. The paper was a key historical milestone in the development of the field of distributed computing, and it is definitely one of the papers that also younger members of our research community should be familiar with.

The 2025 Edsger W. Dijkstra Prize in Distributed Computing Award Committee:
Hagit Attiya, Technion, Israel
Christian Cachin, U. of Bern, Switzerland
Dariusz R. Kowalski, Augusta University, USA
Fabian Kuhn (chair), U. of Freiburg, Germany
Yoram Moses, Technion, Israel
Paul Spirakis, U. of Liverpool, UK