The PODC Influential Paper Award was created to acknowledge an outstanding paper on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade. The following paper received this award at PODC 2002.

Edsger W. Dijsktra, “Self-stabilizing systems in spite of distributed control,” Communications of the ACM 17(11):643-644, 1974 .

Members of the selection committee were Hagit Attiya, Maurice Herlihy, Nancy Lynch, and Keith Marzullo (chair). The following is a description of the winning paper’s contribution, written by Leslie Lamport:

Edsger W. Dijkstra started the field of concurrent and distributed algorithms with his 1965 CACM paper “Solution of a Problem in Concurrent Programming Control”, in which he first stated and solved the mutual exclusion problem. That paper is probably why PODC exists; it certainly inspired most of my work. It remains to this day the most influential paper in the field. That it did not win a PODC Influential Paper Award reflects an artificial separation between concurrent and distributed algorithms–a separation that has never existed in Dijkstra’s work.

The paper that is being honored with this award, “Self-stabilizing Systems in Spite of Distributed Control”, appeared nine years later, in 1974. Nine years after that, in 1983, I made the following remarks about it in a talk at PODC (printed in the 1984 PODC proceedings):

I regard this as Dijkstra’s most brilliant work–at least, his most brilliant published paper. It’s almost completely unknown. I regard it to be a milestone in work on fault tolerance. The terms “fault tolerance” and “reliability” never appear in this paper. In fact, one reason why it’s not better known might be Dijkstra’s approach, illustrated by this quote from the paper:

The appreciation [of these results] is left as an exercise for the reader.

I regard self-stabilization to be a very important concept in fault tolerance, and to be a very fertile field for research. I’ll let you dig out Dijkstra’s paper and discover for yourself what self-stabilization means, and leave it as an exercise for you to appreciate what it has to do with fault tolerance.

These remarks turned out to be one of my most important contributions to computer science, because they helped lead to the rediscovery of this gem of a paper. I am proud to say that my prediction was correct. After a decade of neglect, the concept of self-stabilization introduced by Dijkstra’s paper was recognized as an important concept in fault tolerance and became a fertile research topic. As he had done nine years earlier with mutual exclusion, Dijkstra identified self-stabilization as an important new problem that was not obviously solvable, and he solved it.

---

This page maintained by Gil Neiger.

Last modified: January 23, 2003