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 2024 Edsger W. Dijkstra Prize in Distributed Computing to
Nicola Santoro and Peter Widmayer
for their paper:
“Time is Not a Healer“
Proceedings of the 6th Annual Symposium on
Theoretical Aspects of Computer Science,
pages 304–313, 1989.
The paper introduced the fundamental notion of dynamic transmission faults, with the goal of modeling message losses on a communication channel, in an otherwise synchronous system. As such, it was the first to investigate the impact of a changing communication topology during the execution of the algorithm on the solvability of distributed agreement tasks, complementing the classic processor crash fault model.
Beyond this modeling contribution, the paper also showed, via an elegant proof, the surprising technical fact that, in a system with sufficiently many dynamic transmission faults, a weak version of the Consensus problem is “either trivial or impossible.” More precisely, Consensus is unsolvable in a synchronous system if an adversary is able to cause up to n – 1 messages to be lost in every communication round. This illustrated, for the first time, that the impossibility of Consensus can be also caused by insufficient communication, rather than just the lack of synchrony.
These insights have been very impactful over time, highlighting the connection between the communication topology and the computational power of a distributed system. In turn, the paper has had broad influence across diverse areas such as fault-tolerance, agreement problems, dynamic communication networks, and even topological understanding of distributed computing. The paper has also become a classic text thanks to its excellent exposition.
In summary, the seminal paper by Santoro and Widmayer combines original conceptual contributions with deep theoretical insights, and stands out as a significant stepping stone in our theoretical understanding of distributed computing.
2024 Award Committee:
Dan Alistarh (chair), ISTA
Shlomi Dolev, Ben-Gurion University of the Negev
Faith Ellen, University of Toronto
Fabian Kuhn, University of Freiburg
Petr Kuznetsov, Telecom Paris & Institut Polytechnique Paris
Jukka Suomela, Aalto University