Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0015-3B60-F Versions-Permalink: https://hdl.handle.net/21.11116/0000-000E-5D47-B
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:
ausblenden:
externe Referenz:
https://rdcu.be/dx1Pb (Verlagsversion)
Beschreibung:
-
OA-Status:
Keine Angabe

Urheber

einblenden:
ausblenden:
 Urheber:
Bringmann, Karl1, Autor                 
Doerr, Benjamin1, Autor           
Neumann, Adrian2, Autor
Sliacan, Jakub2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20132013
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Anderer: Local-ID: BB61EAD3E470681BC1257C5C003870CB-BringmannDoerrNeumannSliacan2013
DOI: 10.1007/978-3-642-39206-1_22
BibTex Citekey: BringmannDoerrNeumannSliacan2013
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 40th International Colloquium on Automata, Languages, and Programming
Veranstaltungsort: Riga, Latvia
Start-/Enddatum: 2013-07-08 - 2013-07-12

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Automata, Languages, and Programming
  Kurztitel : ICALP 2013
  Untertitel : 40th International Colloquium, ICALP 2013 ; Riga, Latvia, July 8-12, 2013 ; Proceedings, Part I
Genre der Quelle: Konferenzband
 Urheber:
Fomin, Fedor V.1, Herausgeber
Freivalds, Rusinš1, Herausgeber
Kwiatkowska, Marta1, Herausgeber
Peleg, David1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 255 - 266 Identifikator: ISBN: 978-3-642-39205-4

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 7965 Artikelnummer: - Start- / Endseite: - Identifikator: ISSN: 0302-9743