Tight Bounds on Online Checkpointing Algorithms

Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, Adi Shamir

Abstract

The problem of online checkpointing—maintaining $k$ save points during a computation to minimize rollback distance—has been a subject of study for nearly 50 years. This research settles the problem by proving that the fundamental limit of efficiency (the "discrepancy") is exactly $\ln 4 \approx 1.386$ for large $k$. The authors provide a new recursive algorithm that achieves this bound and identify provably optimal strategies for small numbers of checkpoints ($k \leq 10$).

The Online Checkpointing Problem

Imagine running a massive simulation or a complex cryptographic search that takes weeks to complete. If the system crashes, you want to "roll back" to a previous state rather than starting from scratch. However, memory is finite; you can only store $k$ checkpoints. As the computation progresses, you must decide which old checkpoint to delete to make room for a new one at the current time.

The goal is to keep these $k$ checkpoints as evenly spaced as possible at all times. The efficiency of an algorithm is measured by its "discrepancy": the ratio between the worst-case gap it produces and the "ideal" gap achievable if the total computation time were known in advance.

The basic operation of an online checkpointing algorithm: moving an existing checkpoint (here, $T_2$) to the current time ($t_i$) and re-indexing the remaining points.

Methodology

The researchers employed a multi-faceted approach to solve this long-standing puzzle:

  1. Recursive Geometric Algorithms: They introduced RECURSIVE(G, K), a family of algorithms that move checkpoints based on nested, periodic patterns. By using a geometric progression for update times, they ensured the system remains stable over infinite time.
  2. Linear Programming (LP) Framework: To find the best possible strategies for small $k$ (up to $k=20$), the authors cast the problem as an optimization task. Using the GLPK solver, they identified specific update patterns that minimize discrepancy.
  3. Blocking Sets and $\lambda$-witnesses: To prove the lower bound—that no algorithm can ever beat $\ln 4$—they developed a technique to show that any sequence of moves attempting to be "too efficient" eventually reaches a mathematically impossible state.

Key Insights: The Magic of $\ln 4$

The paper identifies $\ln 4$ as the universal constant for checkpointing. Previous work had placed the bound between 1.30 and 1.59; this research closes that gap entirely for large $k$.

Interestingly, the optimal strategy depends on the number of checkpoints. For $k=2, 3, 5$, simple "Round-Robin" or geometric strategies are optimal. For other values, the patterns become significantly more complex. The authors frame this as an infinite "pebbling game" on a time axis, where the initial state eventually becomes irrelevant as the algorithm reaches a steady-state behavior.

Results and Applications

The study yielded several significant results:

  • Asymptotic Tightness: Proved that for large $k$, the optimal efficiency is exactly $\ln 4$.
  • Optimal Small-k Bounds: Calculated exact efficiencies, such as 1.5 for $k=2$ and approximately 1.467 for $k=10$.
  • Cryptanalysis: Applied to "Floyd’s Cycle-Finding" (used in hash function collision searches), the new strategy reduced wasted evaluation steps by 20% using $k=8$ pointers.
  • Cyber Security: The algorithms can optimize backup strategies against "stealthy" malware. By keeping backups evenly spread in time, users maximize the chance of having a clean recovery point from just before an infection occurred.

Conclusion

By settling the asymptotic bound of online checkpointing at $\ln 4$, this work provides a definitive theoretical foundation for a classical problem. While finding exact optimal patterns for very large $k$ (e.g., $k=100$) remains computationally challenging, the recursive algorithms provided offer a near-optimal solution for practical applications in high-performance computing and security.

Summary updated

Abstract

The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. At ICALP'13 Bringmann et al. studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k, and smaller than ln4-o(1)~~1.39 for the sparse subset of k's which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k. In this paper we solve the main problems left open in the ICALP'13 paper by proving that ln4 is a tight upper and lower bound on the asymptotic discrepancy for all large k, and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k <= 10.
BibTeX
@article{baron2018tight,
  author = {Achiya Bar-On and Itai Dinur and Orr Dunkelman and Rani Hod and Nathan Keller and Eyal Ronen and Adi Shamir},
  title = {{Tight Bounds on Online Checkpointing Algorithms}},
  journal = {ACM Transactions on Algorithms},
  year = {2018},
}
Figure