On thorough garbage collection in distributed systems

In this paper, we consider the hard problem of the thorough garbage collection in uncoordinated checkpointing algorithms. After introduction of the traditional garbage collecting scheme, with which only the obsolete checkpoints can be discarded, we show that this kind of traditional method may fail to discard any checkpoint in some special cases, and point our that it is very necessary and urgent to find a thorough garbage collecting method, with which all the checkpoints useless for any future rollback-recovery including the obsolete ones can be discarded. Then, we propose and prove the Thorough Garbage Collection Theorem, which ensures the feasibility of the thorough garbage collection, and gives the method to calculate the set of the useful checkpoints as well