The Dijkstra Prize Committee has decided to grant the 2018 Edsger W. Dijkstra Prize in Distributed Computing to Bowen Alpern and Fred B. Schneider for their paper:
B. Alpern, F.B. Schneider: Defining liveness, published in Information Processing Letters 21(4), October 1985, pages 181-185.
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.
Concurrent and distributed algorithms today are characterized in terms of safety (“bad things” don’t happen) and liveness (“good things” do happen). This seminal paper is what gave semantic legitimacy to that decomposition. Safety and liveness for concurrent programs had been suggested earlier by Lamport, but liveness was only formally defined for the first time in the winning paper, where it was accompanied by a compelling justification — that every (what we today call a) “trace property” is the conjunction of a safety and a liveness property. The liveness definition and accompanying decomposition theorem thus establish that safety and liveness are not only intuitively appealing but are also formally orthogonal. As a consequence, they constitute the basic building blocks of all (trace) properties and thus underly a substantial number of papers that appeared at PODC and DISC so far.
Moreover, subsequent work has shown that invariants suffice for verifying safety properties and that variant functions on well-founded domains are suitable for verifying liveness properties. So, of the possible ways to decompose properties, the decomposition into safety and liveness provides the added value of also suggesting approaches for verifying each property. Further evidence of the importance of this work is that its topological characterizations and decomposition proof have since been scaled-up to safety and liveness hyperproperties, which express confidentiality and other important correctness concerns that trace properties cannot.
The E.W. Dijkstra 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 PODC to be held at Royal Holloway, University of London, Egham, United Kingdom, July 23-27, 2018.
The 2018 Dijkstra Prize Committee:
- Yehuda Afek, Tel-Aviv University
- Idit Keidar, Technion
- Boaz Patt-Shamir, Tel-Aviv University
- Sergio Rajsbaum, UNAM
- Ulrich Schmid (chair), TU Wien
- Gadi Taubenfeld, IDC Herzliya