Safe and complete distributed garbage collection with the train algorithm

Abstract

A new mechanism for achieving isolated train detection in the distributed train algorithm is presented. The train algorithm is a general strategy for garbage collection, and the task of isolated train detection is a portion of the strategy which allows complete collection. When the train algorithm is deployed in a distributed system, a distributed algorithm is required to solve isolated train detection. We analyse the distributed train algorithm in the context of its isolated train detection aspect. We determine how it can be construed within the paradigm underlying distributed termination detection algorithms. From this we form a technical framework which allows any algorithmfrom this class to be used, essentially unmodified, to solve the distributed isolated train detection problem. We demonstrate this by deriving a new mechanism from a distributed termination detection algorithm.