Modelling a Distributed Cached Store for Garbage Collection

Caching and persistence support efficient, convenient and transparent distributed data sharing. The most natural model of persistence is persistence by reachability, managed automatically by a garbage collector (GC). We propose a very general model of such a system (based on distributed shared memory) and a scalable, asynchronous distributed GC algorithm. Within this model, we prove formally the safety of the GC, and show sufficient and widely applicable correctness conditions for the interactions between applications, store, memory, coherence, and GC. The GC runs as a set of processes (local to each participating machine) communicating by asynchronous messages. Collection does not interfere with applications by setting locks, polluting caches, or causing I/O; this requirement raised some novel and interesting challenges which we address in this article. The algorithm is safe and live; it is not complete, i.e. it does not collect distributed cycles of garbage. 1 Introduction We presen..