Collecting cyclic distributed garbage by controlled migration
Umesh Maheshwari, Barbara H. Liskov · 1995
Distributedreference counting provides timely and fault-tolerant '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 umecessary 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.