The derivation of graph marking algorithms from distributed termination detection protocols

https://doi.org/10.1016/0167-6423(88)90024-XGet rights and content
Under an Elsevier user license
open archive

Abstract

We show that on-the-fly garbage collection algorithms can be obtained by transforming distributed termination detection protocols. Virtually all known on-the-fly garbage collecting algorithms are obtained by applying the transformation. The approach leads to a novel and insightful derivation of, e.g., the concurrent garbage collection algorithms of Dijkstra et al. and of Hudak and Keller. The approach also leads to several new, highly parallel algorithms for concurrent garbage collection. We also analyze a garbage collecting system due to Hughes from our current perspective.

Cited by (0)

This work was carried out while the second author visited the University of Utrecht, supported by a grant from the Netherlands Organization for the Advancement of Pure Research (ZWO).

∗∗

UUCP address..!mcvax!ruuinfvax!gerard. Work supported by the Netherlands Organization for the Advancement of Pure Research (ZWO).

∗∗∗

Department of Mathematics and Computer Science, University of Sciences and Arts of Oklahoma, Chickasha, OK 73018, U.S.A.