Online Checkpointing with Improved Worst-Case Guarantees
Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan
INFORMS Journal on Computing · 2015 · Volume 27 · Issue 3
Abstract
In the online checkpointing problem, the task is to continuously maintain a set of k checkpoints that allow rewinding an ongoing computation faster than by a full restart. The only operation allowed is to replace an old checkpoint by the current state. Our aim is 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 few as possible. In particular, we want the closest checkpoint earlier than t to be no farther away from t than q k times the ideal distance T /( k + 1), where q k is a small constant. Improving earlier work showing 1 + 1/ k ≤ q k ≤ 2, we show that q k can be chosen asymptotically less than 2. We present algorithms with asymptotic discrepancy q k ≤ 1.59 + o (1) valid for all k and q k ≤ ln(4) + o (1) ≤ 1.39 + o (1) valid for k being a power of two. Experiments indicate the uniform bound p k ≤ 1.7 for all k . For small k , we show how to use a linear programming approach to compute good checkpointing algorithms. This gives discrepancies of less than 1.55 for all k < 60. We prove the first lower bound that is asymptotically more than 1, namely q k ≥ 1.30 − o (1). We also show that optimal algorithms (yielding the infimum discrepancy) exist for all k .
Keywords
bounded memory, breakpoints, empirical evaluation
Enable JavaScript for citation tools and additional paper interactions.