de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Online Checkpointing with Improved Worst-case Guarantees

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44182

Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons71827

Neumann,  Adrian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons79491

Sliacan,  Jakub
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Bringmann, K., Doerr, B., Neumann, A., & Sliacan, J. (2015). Online Checkpointing with Improved Worst-case Guarantees. INFORMS Journal on Computing, 27(3), 478-490. doi:10.1287/ijoc.2014.0639.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0029-01E0-A
Zusammenfassung
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.