The Derivation of Distributed Termination Detection Algorithms from Garbage 
Collection Schemes 

ACM TOPLAS 15:1, pp. 1-35, January 1993 

It is shown that the termination detection problem for distributed 
computations can be modeled as an instance of the garbage collection problem. 
Consequently, algorithms for the termination detection problem are obtained by 
applying transformations to garbage collection algorithms. The transformation 
can be applied to collectors of the "mark-and-sweep" type as well as to 
reference counting garbage collectors. As examples, the scheme is used to 
transform the distributed reference counting protocol of Lermen and Maurer, 
the weighted reference counting protocol, the local reference counting 
protocol, and Ben-Ari's mark-and-sweep collector into termination detection 
algorithms. Known termination detection algorithms as well as new variants 
are obtained.