ONLINE ALGORITHMS FOR LOCATING CHECKPOINTS

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 chec kpoints allow faster recomputation of arbitrary requested points withi n the computation. We abstract the problem to a server problem in whic h k servers move along a line in a single direction, modeling the fact that most computations are not reversible. Since checkpoints may be a rbitrarily copied, we allow a server to jump to any location currently occupied by another server. We present on-line algorithms and analyze their competitiveness. We give lower bounds on the competitiveness of any on-line algorithm and show that our algorithms achieve these boun ds within relatively small factors.