Derivation of Graph Marking Algorithms from Distributed Termination Detection Protocols

摘要

Shown was 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. Also analyzed was a garbage collecting system due to Hughes from the current perspective.