Tight Bounds on Online Checkpointing Algorithms

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



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.13.pdf
  • Filesize: 487 kB
  • 13 pages

Document Identifiers

Author Details

Achiya Bar-On
  • Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel
Itai Dinur
  • Computer Science Department, Ben-Gurion University, Beer Sheva, Israel
Orr Dunkelman
  • Computer Science Department, University of Haifa, Haifa, Israel
Rani Hod
  • Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel
Nathan Keller
  • Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel
Eyal Ronen
  • Computer Science Department, The Weizmann Institute, Rehovot, Israel
Adi Shamir
  • Computer Science Department, The Weizmann Institute, Rehovot, Israel

Cite AsGet BibTex

Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, and Adi Shamir. Tight Bounds on Online Checkpointing Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.13

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • checkpoint
  • checkpointing algorithm
  • online algorithm
  • uniform distribution
  • discrepancy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Lauri Ahlroth, Olli Pottonen, and André Schumacher. Approximately Uniform Online Checkpointing with Bounded Memory. Algorithmica, 67(2):234-246, 2013. URL: http://dx.doi.org/10.1007/s00453-013-9772-5.
  2. M.S. Andersen, J. Dahl, and L. Vandenberghe. CVXOPT: A Python package for convex optimization, 2016. version 1.1.9. Available at URL: http://cvxopt.org.
  3. Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, and Madhu Sudan. On-Line Algorithms for Locating Checkpoints. Algorithmica, 11(1):33-52, 1994. URL: http://dx.doi.org/10.1007/BF01294262.
  4. Karl Bringmann, Benjamin Doerr, Adrian Neumann, and Jakub Sliacan. Online Checkpointing with Improved Worst-Case Guarantees. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 255-266, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_22.
  5. K. Mani Chandy and Chittoor V. Ramamoorthy. Rollback and Recovery Strategies for Computer Programs. IEEE Trans. Computers, 21(6):546-556, 1972. URL: http://dx.doi.org/10.1109/TC.1972.5009007.
  6. Free Software Foundation. Gnu linear programming kit, 2012. Version 4.61, URL: http://www.gnu.org/software/glpk/.
  7. Erol Gelenbe. On the Optimum Checkpoint Interval. J. ACM, 26(2):259-270, 1979. URL: http://dx.doi.org/10.1145/322123.322131.
  8. Sam Toueg and Özalp Babaoglu. On the Optimum Checkpoint Selection Problem. SIAM J. Comput., 13(3):630-649, 1984. URL: http://dx.doi.org/10.1137/0213039.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail