Modelling a Distributed Cached Store for Garbage Collection: the algorithm and its correctness proof

Paulo Ferreira 1 Marc Shapiro 1
1 SOR - Distributed Object Systems
Inria Paris-Rocquencourt
Abstract : 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 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 collects some distributed cycles of garbage but not necessarily all.
Keywords : gc mem rep
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01248219
Contributor : Alain Monteil <>
Submitted on : Thursday, December 24, 2015 - 9:43:35 AM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM

File

MDCSGC_ecoop98.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Paulo Ferreira, Marc Shapiro. Modelling a Distributed Cached Store for Garbage Collection: the algorithm and its correctness proof. Euro. Conf. on Object-Oriented Pging. (ECOOP), 1998, Brussels, Belgium. pp.234--259, ⟨10.1007/BFb0054094⟩. ⟨hal-01248219⟩

Share

Metrics

Record views

320

Files downloads

127