Collecting cyclic distributed garbage by controlled migration

Distributed reference counting provides timely and faulttolerant garbage collection in large distributed systems, but it fails to collect cyclic garbage distributed across nodes. A common,proposal is to migrate all objects on a garbage cycle to a single node, where they can be collected by the local collector. However, existing schemes have practical problems due to unnecessary,migration of objects. We present solutions to these problems: our scheme avoids migration of live objects, batches objects to avoid a cascade of migration messages, 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 migrated. The scheme has low overhead, and it preserves the decentralized and fault-tolerant nature of distributed reference counting and migration.