Collecting Distributed Garbage Cycles by Back Tracing

“Collecting Distributed Garbage Cycles by Back Tracing” by Umesh Maheshwari and Barbara Liskov. In ACM Symposium on Principles of Distributed Computing (PODC), (Santa Barbara, CA), Aug. 1997, pp. 239-248.

Abstract

Systems that store objects at a large number of sites require fault-tolerant and timely garbage collection. A popular technique is to trace each site independently using inter-site references as roots. However, this fails to collect cyclic garbage spread across sites. We present an algorithm that collects cyclic garbage by involving only the sites containing it. Our algorithm is based on finding objects highly likely to be cyclic garbage and tracing backward from them to check if they are reachable from any root. We present efficient techniques that make conducting such traces practical. The algorithm collects all distributed cyclic garbage, is safe in the presence of concurrent mutations, and has low space and time overhead.

BibTeX entry:

@inproceedings{maheshwari97collecting,
   author = {Umesh Maheshwari and Barbara Liskov},
   title = {Collecting Distributed Garbage Cycles by Back Tracing},
   booktitle = {ACM Symposium on Principles of Distributed Computing (PODC)},
   pages = {239--248},
   address = {Santa Barbara, CA},
   month = aug,
   year = {1997},
   url = {http://citeseer.ist.psu.edu/maheshwari97collecting.html}
}