On-the-fly Garbage Collection: an Exercise in Cooperation

This paper presents the first concurrent garbage collection algorithm–that is, an algorithm in which the collector operates concurrently with the process that creates the garbage. The paper is fairly well known; its history is not.

I received an early version of the paper from Dijkstra, and I made a couple of suggestions. Dijkstra incorporated them and, quite generously, added me to the list of authors. He submitted the paper to CACM. The next I heard about it was when I received a copy of a letter from Dijkstra to the editor withdrawing the paper. The letter said that someone had found an error in the algorithm, but gave no indication of what the error was. Since Dijkstra’s proof was so convincing, I figured that it must be a trivial error that could easily be corrected.

I had fairly recently written [23]. So, I decided to write a proof using that proof method, thinking that I would then find and correct the error. In about 15 minutes, trying to write the proof led me to the error. To my surprise, it was a serious error.

I had a hunch that the algorithm could be fixed by changing the order in which two operations were performed. But I had no good reason to believe that would work. Indeed, I could see no simple informal argument to show that it worked. However, I decided to go ahead and try to write a formal correctness proof anyway. It took me about two days of solid work, but I constructed the proof. When I was through, I was convinced that the algorithm was now correct, but I had no intuitive understanding of why it worked.

In the meantime, Dijkstra figured out that the algorithm could be fixed by interchanging two other operations, and he wrote the same kind of behavioral proof as before. His fix produced an arguably more efficient algorithm than mine, so that’s the version we used. I sketched an assertional proof of that algorithm. Given the evidence of the unreliability of his style of proof, I tried to get Dijkstra to agree to a rigorous assertional proof. He was unwilling to do that, though he did agree to make his proof somewhat more assertional and less operational. Here are his comments on that, written in July, 2000:
There were, of course, two issues at hand: (A) a witness showing that the problem of on-the-fly garbage collection with fine-grained interleaving could be solved, and (B) how to reason effectively about such artifacts. I am also certain that at the time all of us were aware of the distinction between the two issues. I remember very well my excitement when we convinced ourselves that it could be done at all; emotionally it was very similar to my first solutions to the problem of self-stabilization. Those I published without proofs! It was probably a period in my life that issue (A) in general was still very much in the foreground of my mind: showing solutions to problems whose solvability was not obvious at all. It was more or less my style. I had done it (CACM, Sep. 1965) with the mutual exclusion.

I, too, have always been most interested in showing that something could be done, rather than in finding a better algorithm for doing what was known to be possible. Perhaps that is why I have always been so impressed by the brilliance of Dijkstra’s work on concurrent algorithms.
David Gries later published an Owicki-Gries style proof of the algorithm that was essentially the same as the one I had sketched. He simplified things a bit by combining two atomic operations into one. He mentioned that in a footnote, but CACM failed to print the footnote. (However, they did print the footnote number in the text.)

The lesson I learned from this is that behavioral proofs are unreliable and one should always use state-based reasoning for concurrent algorithms–that is, reasoning based on invariance.