Collecting distributed garbage cycles by back tracing
Umesh Maheshwari, Barbara H. Liskov · 1997
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. 1 Introduction Emerging distributed systems will use objects stored at a large number of sites. The scale of such systems poses new challenges to reclaiming the storage of objects unreachable by applications. Such objects are known as garbage. A simple way to col...