In this paper, the hard problem of thethorough garbage collection in uncoordinated checkpointing algorithms isstudied. After introduction of the traditional garbage collectingscheme, with which only obsolete checkpoints can be discarded, it isshown that this kind of traditional method may fail to discard anycheckpoint in some special cases, and it is necessary and urgent to finda thorough garbage collecting method, with which all the checkpointsuseless for any future rollback-recovery including the obsolete ones canbe discarded. Then, the Thorough Garbage Collection Theorem is proposedand proved, which ensures the feasibility of the thorough garbagecollection, and gives the method to calculate the set of the usefulcheckpoints as well.