The derivation of graph marking algorithms from distributed termination detection protocols

DOI10.1016/0167-6423(88)90024-XMaRDI QIDQ1104744zbMATH OpenOpenAlexFDO

Authors Gerard Tel, Richard B. Tan, J. Van Leeuwen

Publication date 1988

Published in Science of Computer Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6423(88)90024-x

zbMATH Keywords

concurrent garbage collectiondistributed termination detection protocolshighly parallel algorithmson-the-fly garbage collection

Mathematics Subject Classification ID

Theory of operating systems (68N25) Graph theory (including graph drawing) in computer science (68R10)

Review text

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 Kelle. 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 concurrent perspective.

Recommendations

• scientific article; zbMATH DE number 3990849
• scientific article; zbMATH DE number 3997151
• On-the-fly garbage collection for several mutators
• scientific article; zbMATH DE number 2016070
• Algorithms for on-the-fly garbage collection

Cited in

(5)

• scientific article; zbMATH DE number 3990849 (Why is no real title available?)
• scientific article; zbMATH DE number 3997151 (Why is no real title available?)
• Concurrent garbage collection for concurrent rewriting
• A scalable algorithm for decentralized actor termination detection
• Strong stable properties in distributed systems

This page was built for publication: The derivation of graph marking algorithms from distributed termination detection protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104744)