COLLECTING CYCLIC DISTRIBUTED GARBAGE BY CONTROLLED MIGRATION

Distributed systems with a large number of nodes use internode referen ce counting for timely and fault-tolerant garbage collection. However, this fails to collect cyclic garbage distributed across nodes. One fi x is to migrate all objects on a garbage cycle to a single node, where they can be collected by the tracing-based local collector. Existing proposals based on this technique have practical problems due to unnec essary migration of objects. We propose a scheme that avoids migration of live objects, batches objects to avoid a cascade of migration mess ages, and short-cuts the migration path to avoid multiple migrations. We use simple estimates to detect objects that are highly likely to be cyclic garbage and to select a node to which such objects are migrate d. The scheme collects all distributed cyclic garbage, has low overhea d, and preserves the decentralized and fault-tolerant nature of distri buted reference counting and migration.