Cyclic Distributed Garbage Collection without Global Synchronization

In this report we show an algorithm for cyclic distributed garbage collection that does not require global coordination and is tolerant to message, network, and process failures. Most of the cyclic distributed garbage collectors use mark-and-sweep to find the transitive closure of objects that are reached from the global roots. The main disadvantage of mark-and-sweep is that it requires global coordination to know when the mark-phase has ended. Our algorithm takes a more radical approach and uses back-tracing instead of mark-and-sweep to eliminate the need for global synchronization. Starting from an object that is suspected to be garbage, the algorithm recursively traces back the references that point to the suspect to find the transitive closure of objects that reach the suspect. If this closure does not contain any root, then the objects in the closure are collected. Local garbage collectors have to be modified to provide back-references for local proxies (representation of remote o..