Collecting Cyclic Distributed garbage by Controlled Migration

“Collecting Cyclic Distributed garbage by Controlled Migration” by Umesh Maheshwari and Barbara Liskov. In Proceedings of Principles of Distributed Computing (PODC), 1995. Best student paper award.

Abstract

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.

BibTeX entry:

@inproceedings{maheshwari95collecting,
   author = {Umesh Maheshwari and Barbara Liskov},
   title = {Collecting Cyclic Distributed garbage by Controlled Migration},
   booktitle = {Proceedings of Principles of Distributed Computing (PODC)},
   year = {1995},
   note = {Best student paper award},
   url = {http://citeseer.ist.psu.edu/maheshwari95collecting.html}
}