Online Checkpointing with Improved Worst-Case Guarantees

摘要: In the online checkpointing problem, task is to continuously maintain a set of k checkpoints that allow rewinding an ongoing computation faster than by full restart. The only operation allowed replace old checkpoint current state. Our aim placement strategies minimize cost, i.e., such at all times T when requested rewind some time t ≤ number steps need be redone get from before as few possible. particular, we want closest earlier no farther away qk ideal distance T/k + 1, where small constant. Improving work showing 1 1/k 2, show can chosen asymptotically less 2. We present algorithms with asymptotic discrepancy 1.59 o1 valid for and ln4 1.39 being power two. Experiments indicate uniform bound pk 1.7 k. For k, how use linear programming approach compute good algorithms. This gives discrepancies 1.55 < 60. We prove first lower more namely ≥ 1.30-o1. also optimal yielding infimum exist