English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  Online Checkpointing with Improved Worst-case Guarantees

Bringmann, K., Doerr, B., Neumann, A., & Sliacan, J. (2013). Online Checkpointing with Improved Worst-case Guarantees. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, Languages, and Programming (pp. 255-266). Berlin: Springer. doi:10.1007/978-3-642-39206-1_22.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0015-3B60-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-A276-4
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Bringmann, Karl1, Author           
Doerr, Benjamin1, Author           
Neumann, Adrian2, Author
Sliacan, Jakub2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: In the online checkpointing problem, the task is to continuously maintain a set of k checkpoints that allow to rewind 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 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 q_k times the ideal distance T / (k+1), where q_k is a small constant. Improving over 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 one, namely q_k ≥ 1.30 - o(1). We also show that optimal algorithms (yielding the infimum discrepancy) exist for all~k.

Details

show
hide
Language(s): eng - English
 Dates: 20132013
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: Other: Local-ID: BB61EAD3E470681BC1257C5C003870CB-BringmannDoerrNeumannSliacan2013
DOI: 10.1007/978-3-642-39206-1_22
BibTex Citekey: BringmannDoerrNeumannSliacan2013
 Degree: -

Event

show
hide
Title: 40th International Colloquium on Automata, Languages, and Programming
Place of Event: Riga, Latvia
Start-/End Date: 2013-07-08 - 2013-07-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: Automata, Languages, and Programming
  Abbreviation : ICALP 2013
  Subtitle : 40th International Colloquium, ICALP 2013 ; Riga, Latvia, July 8-12, 2013 ; Proceedings, Part I
Source Genre: Proceedings
 Creator(s):
Fomin, Fedor V.1, Editor
Freivalds, Rusinš1, Editor
Kwiatkowska, Marta1, Editor
Peleg, David1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 255 - 266 Identifier: ISBN: 978-3-642-39205-4

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 7965 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743