Online Checkpointing with Improved Worst-Case Guarantees

The only operation allowed is to remove an old checkpoint and to store the current state instead. Our aim are checkpoint placement strategies that minimize rewinding cost, i.e., such that at all times T when requested to rewind to some time t <= T the number of computation steps that need to be redone to get to t from a checkpoint before t is as small as possible.
In particular, we want that the closest checkpoint earlier than t is not further away from t than p_k times the ideal distance T / (k+1), where p_k is a small constant.
Improving over earlier work showing 1 + 1/k <= p_k <= 2, we show that p_k can be chosen less than 2 uniformly for all k. More precisely, we show the uniform bound p_k <= 1.7 for all k, and present algorithms with asymptotic performance p_k <= 1.59 + o(1) valid for all k and p_k <= ln(4) + o(1) <= 1.39 + o(1) valid for k being a power of two. For small values of k, we show how to use a linear programming approach to compute good checkpointing algorithms. This gives performances of less than 1.53 for k <= 10.
One the more theoretical side, we show the first lower bound that is asymptotically more than one, namely p_k >= 1.30 - o(1). We also show that optimal algorithms (yielding the infimum performance) exist for all k.

http://arxiv.org/abs/1302.4216