The Edsger W. Dijkstra Prize in Distributed Computing was created to acknowledge 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. The Prize is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). This award is presented annually, with the presentation taking place alternately at PODC and DISC.
The 2017 Award Committee, composed of Alexander Schwarzmann (Chair), Marcos K. Aguilera, Alessandro Panconesi, Andrzej Pelc, Andrea Richa, and Roger Wattenhofer, has selected
Elizabeth Borowsky and Eli Gafni
to receive the 2017 Edsger W. Dijkstra Prize in Distributed Computing for the outstanding paper:
Elizabeth Borowsky, Eli Gafni:
Generalized FLP impossibility result for
t-resilient asynchronous computations.
Proceedings of the 25th Annual ACM Symposium
on Theory of Computing (STOC 1993),
pages 91–100, 1993.
This is a fundamental paper in the original sense. It contains two breakthrough contributions. First, it lays a new concept of read-write simulations in the very foundation of distributed computing. Second, it introduces the immediate-snapshot model. For the first contribution, the paper argues that, even though distributed systems exhibit multiple seemingly incomparable instantiations, they operate on the same fundamental principles. By deriving these principles, we could obtain computability and complexity results concerning a given specific distributed system via simulations and reductions.
The paper illustrates this approach by proposing an ingenious simulation tool, now commonly referred to as the BG Simulation. The tool allows a system of k + 1 processes to consistently simulate algorithms designed for any k-resilient system. The BG Simulation proved to be instrumental in establishing impossibility results and building reductions between them. In particular, this paper uses the BG Simulation to derive the fundamental impossibility of k-resilient k-set consensus from the impossibility of wait-free set consensus.
The second key contribution, the immediate-snapshot model, leads to a simple and elegant combinatorial characterization of the set of runs of a protocol. This characterization then leads to the impossibility of wait-free set consensus through a simple application of Sperner’s Lemma.
These two points—the use of a simpler model of computation to establish the wait-free set-consensus impossibility and the use of simulation to derive the generalized k-resilient impossibility from the wait-free one—distinguishes this paper from two concurrent papers appeared at STOC 1993, by Herlihy and Shavit and by Saks and Zaharoglou, journal versions of which were later awarded the prestigious Gödel prize.
Since 1993, both contributions of this paper were widely adopted by the distributed-computing community. The illuminating BG Simulation technique gave rise to a broad spectrum of results in various contexts: from adversarial shared-memory computing to mobile Byzantine robots. The BG simulation and abstractions around it establish now the very basis of the state-of-the-art research field of distributed computability theory. The (iterated) immediate-snapshot model is widely adopted nowadays in combinatorial representations of distributed computations. As was correctly conjectured by the authors in a concurrent paper, the protocol complex of this model is precisely captured by the standard chromatic subdivision, enabling straightforward reasoning about the model’s computability. The two contributions also help us in teaching the foundations of resilience: it is much easier to deal with the wait-free model, and deduce computability of other models via simulation.
In summary, this paper turned out to be crucial for our understanding of fault-tolerant distributed computing. It proposed a powerful reduction technique, the BG simulation, it introduced the immediate-snapshot model, and it established the fundamental impossibility of k-resilient k-set consensus.
Yehuda Afek, Tel Aviv University, Israel
Rachid Guerraoui, EPFL, Switzerland
Taisuke Izumi, Nagoya Institute of Technology, Japan
Petr Kuznetsov, Télécom ParisTech, France