The authors describe a garbage collection scheme for managing a distributed object store in which accessible objects survive system failures. The scheme is based on copying garbage collection and has the following advantages: it is tolerant to node failures, a fail-stop behavior of the node is assumed; it is partial, a given execution of the distributed garbage collection does not need to involve all the nodes, that is, the garbage collector can collect garbage on a subset of the entire system nodes; it minimizes disk accesses; it can collect any kind of cycles both within a node and among different nodes; it uses the depth-first-search to increase locality; it is iterative and it does not assume any particular primitives of the operating system of a node. In addition this distributed garbage collector can be extended to be asynchronous, that is, every node can decide to begin the collection at any time independently of the others.
展开▼