2018 Edsger W. Dijkstra Prize in Distributed Computing

Apr 30, 2018

The E.W. Dijkstra 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. The 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.

The 2018 Dijkstra Prize Committee consisted of 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).

The 2018 Edsger W. Dijkstra Prize in Distributed Computing goes to

Bowen Alpern
&
Fred B. Schneider

for their paper:

Defining liveness

published in

Information Processing Letters 21(4), October 1985.

 

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 2018  Edsger W. Dijkstra Prize in Distributed Computing will be presented at PODC, to be held at Royal Holloway, University of London, Egham, United Kingdom, July 23-27, 2018.