On Self-stabilizing Systems

This note was written upon reading Dijkstra’s classic paper “Self-stabilizing Systems in Spite of Distributed Control” that appeared in the November 1974 issue of CACM (see [58]). It generalizes one of the algorithms in Dijkstra’s paper from a line of processes to an arbitrary tree of processes. It also discusses the self-stabilizing properties of the bakery algorithm. I never tried to publish this note–probably because I regarded it as too small a piece of work to be worth a paper by itself.

The note contains the intriguing sentence: “There is a complicated modified version of the bakery algorithm in which the values of all variables are bounded.” I never wrote down that version, and I’m not sure what I had in mind. But I think I was thinking of roughly the following modification. As a process waits to enter its critical section, it keeps reducing its number, not entering the critical section until its number equals one. A process p can reduce its number by at most one, and only when the next lower-numbered process’s number is at least two less than p’s number, and the next higher-numbered process is within one of p’s number. I think I intended to use the techniques of [25] to allow reading and writing of numbers to remain non-atomic while maintaining the order of waiting processes. (If eventually all processes stop changing their numbers, then all processes will eventually read the correct numbers, allowing some process to progress.) At one time, I convinced myself that this algorithm is correct. But I never wrote a rigorous proof, so I don’t know if it really works. Filling in the details and proving correctness should be a nice exercise.