The 2015 Edsger W. Dijkstra Prize in Distributed Computing

The E. W. Dijkstra Prize Committee has decided to grant the 2015 Edsger W. Dijkstra Prize in Distributed Computing jointly to the following two papers:

  • Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols, by Michael Ben-Or, published in Proceedings of the Second ACM Symposium on Principles of Distributed Computing, pages 27-30, August 1983
  • Randomized Byzantine Generals, by Michael O. Rabin, published in Proceedings of Twenty-Fourth IEEE Annual Symposium on Foundations of Computer Science, pages 403- 409, November 1983

The Prize is awarded 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.

In these seminal papers, published in close succession in 1983, Michael Ben-Or and Michael O. Rabin started the field of fault-tolerant randomized distributed algorithms.

In 1983, randomized algorithms, still in their infancy, were starting to make headway in sequential algorithms and complexity theory. The role of randomization at that time was to improve the complexity of solving certain problems. It was shown that problems, such as primality testing, that were deterministically solvable with a given time or space complexity, could be solved in less time or space by allowing the algorithm to make random choices.

Ben-Or and Rabin were the first to use randomness to solve to a problem, consensus in an asynchronous distributed system subject to failures, which had provably no deterministic solution. In other words, they were addressing a computability question and not a complexity one, and the answer was far from obvious.

Underlying both algorithms is the notion of a shared coin, i.e., a mechanism that enables separate processes to make a common random choice.

Ben-Or's solution is fully distributed and relies on no assumptions, but requires a potentially exponential series of independent coin tosses to implement a shared coin. Rabin's solution uses cryptographic techniques to implement the shared coin in constant time. Ben-Or and Rabin's algorithms opened the way to a large body of work on randomized distributed algorithms in asynchronous systems, not only on consensus, but also on both theoretical problems, such as renaming, leader election, and snapshots, as well as applied topics, such as dynamic load balancing, work distribution, contention reduction, and coordination in concurrent data structures.

The E.W. Prize 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. This year it will be presented at DISC, to be held at Tokyo, Japan, October 5-9, 2015.

Dijkstra Prize Committee 2015
James Aspnes, Yale
Pierre Fraigniaud, University of Paris Diderot
Rachid Guerraoui, EPFL
Nancy Lynch, MIT
Yoram Moses, Technion
Paul Spirakis, University of Liverpool and CTI, Chair your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.