Solved Problems, Unsolved Problems and NonProblems in Concurrency
Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing |
This is the invited address I gave at the 1983 PODC conference, which I transcribed from a tape recording of my presentation. The first few minutes of the talk were not taped, so I had to reinvent the beginning. This talk is notable because it marked the rediscovery by the computer science community of Dijkstra’s 1974 CACM paper that introduced the concept of self-stabilization. A self-stabilizing system is one that, when started in any state, eventually “rights itself” and operates correctly. The importance of self-stabilization to fault tolerance was obvious to me and a handful of people, but went completely over the head of most readers. Dijkstra’s paper gave little indication of the practical significance of the problem, and few people understood its importance. So, this gem of a paper had disappeared without a trace by 1983. My talk brought Dijkstra’s paper to the attention of the PODC community, and now self-stabilization is a regular subfield of distributed computing. I regard the resurrection of Dijkstra’s brilliant work on self-stabilization to be one of my greatest contributions to computer science.
The paper contains one figure–copied directly from a transparency–with an obviously bogus algorithm. I tried to recreate an algorithm from memory and wrote complete nonsense. It’s easy to make such a mistake when drawing a transparency, and I probably didn’t bother to look at it when I prepared the paper. To my knowledge, it is the only incorrect algorithm I have published.
Copyright © 1984 by the Association for Computing Machinery, Inc.Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org. The definitive version of this paper can be found at ACM's Digital Library --http://www.acm.org/dl/.