Tight Upper Bound on Useful Distributed System Checkpoints
Yi‐Min Wang, Pi-Yu Chung, W.K. Fuchs · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1995
Continue on reverse If necessary and identify by block number)fault tolerance, checkpointing, garbage collection, distributed systems, algorithms '.9. ABSTRACT (Continue on reverse if necessary and identify by block number)Optimal garbage collection for distributed system checkpoints had remained an open problem.Existing algorithms may need to retain an unbounded number of non-obsolete checkpoints.We derive a polynomial time optimal garbage collection algorithm, and prove that the number of useful checkpoints is bounded by + l)/2 , where N is the number of processes, and the bound is tight.Experimental results based on real programs demonstrate the significant advantage of the algorithm.