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:
- Michael Ben-Or, “Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols“, in Proceedings of the Second ACM Symposium on Principles of Distributed Computing, pages 27-30, August 1983.
- Michael O. Rabin, “Randomized Byzantine Generals“, in Proceedings of Twenty-Fourth IEEE Annual Symposium on Foundations of Computer Science, pages 403-409, November 1983.
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 2015 Dijkstra Prize Committee:
- Paul Spirakis (Univ. of Liverpool and CTI, Chair)
- James Aspnes (Yale)
- Pierre Fraigniaud (Univ. of Paris Diderot)
- Rachid Guerraoui (EPFL)
- Nancy Lynch (MIT)
- Yoram Moses (Technion)
The 2015 Dijkstra Prize award will be presented at DISC 2015.
