Incremental distribution of timestamp packets: a new approach to distributed garbage collection

Abstract

A new algorithm for distributed garbage collection is presented. This algorithm collects distributed garbage incrementally and concurrently with user activity. It is the first incremental algorithm that is capable of collecting cyclic distributed garbage. Computational and network communication overhead are acceptable. Hosts may be temporarily inaccessible and synchronization between hosts is not necessary. The algorithm is based on asynchronous distribution of timestamp packets each containing a list of last-access times of some relevant remotely referenced objects. Finally, the correctness and time complexity of the algorithm are discussed.