Affordable Access

Publisher Website

The derivation of graph marking algorithms from distributed termination detection protocols

Authors
Journal
Science of Computer Programming
0167-6423
Publisher
Elsevier
Publication Date
Volume
10
Issue
2
Identifiers
DOI: 10.1016/0167-6423(88)90024-x
Disciplines
  • Computer Science

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.