School of Computing

Cyclic distributed garbage collection with group merger

Helena C.C.D. Rodrigues and Richard E. Jones

Technical Report 17-97, Computing Laboratory, University of Kent at Canterbury, December 1997.


This paper presents a new algorithm for distributed garbage collection and outlines its implementation within the Network Objects system. The algorithm is based on a reference listing scheme, which is augmented by partial tracing in order to collect distributed garbage cycles. Our collector is designed to be flexible, allowing efficiency, expediency and fault-tolerance to be traded against completeness. Processes may be dynamically organised into groups, according to appropriate heuristics, in order to reclaim distributed garbage cycles. Unlike previous group-based algorithms, multiple concurrent distributed garbage collections that span groups are supported: when two collection meet they may either merge, overlap or retreat. The algorithm places no overhead on local collectors and suspends local mutators only briefly. Partial tracing of the distributed graph involves only objects thought to be part of a garbage cycle: no collaboration with other processes is required.

Download publication 99 kbytes

Bibtex Record

author = {Helena C.C.D. Rodrigues and Richard E. Jones},
title = {Cyclic Distributed Garbage Collection with Group Merger},
month = {December},
year = {1997},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {},
    institution = {Computing Laboratory, University of Kent at Canterbury},
    number = {17-97},

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014