Online algorithms for locating checkpoints
Marshall W. Bern, Daniel Greene, Arvind U. Raghunathan, Madhu Sudan · 1990
Motivated by applications in data compression, debugging, and physical simulation, we consider the problem of adaptively choosing locations in a long computation at which to save intermediate results.Such checkpoints allow faster recomputation of arbitrary requested points within the computation.We abstract the problem to a server problem in which k servers move along a line in a single direction, modeling the fact that most computations are not reversible.Since checkpoints may be arbitrarily copied, we allow a server to jump to any location currently occupied by another server.We present online algorithms and analyze their competitiveness.We give lower bounds on the competitiveness of any online algorithm and show that our algorithms achieve these bounds within relatively small factors.