Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 Author, Editor
 Author(s): Bringmann, Karl Doerr, Benjamin Neumann, Adrian Sliacan, Jakub dblp dblp dblp dblp Not MPG Author(s): Sliacan, Jakub
 Editor(s): Fomin, Fedor V. Freivalds, Rūsiņš Kwiatkowska, Marta Peleg, David dblp dblp dblp dblp Not MPII Editor(s): Fomin, Fedor V. Freivalds, Rūsiņš Kwiatkowska, Marta Peleg, David
 BibTeX cite key*: BringmannDoerrNeumannSliacan2013
 Title, Booktitle
 Title*: Online Checkpointing with Improved Worst-Case Guarantees Booktitle*: Automata, Languages, and Programming - 40th International Colloquium (ICALP 2013)
 Event, URLs
 Conference URL:: http://icalp2013.lu.lv/ Downloading URL: http://arxiv.org/pdf/1302.4216v2 Event Address*: Riga, Latvia Language: English Event Date* (no longer used): Organization: European Association for Theoretical Computer Science (EATCS) Event Start Date: 8 July 2013 Event End Date: 12 July 2013
 Publisher
 Name*: Springer URL: http://springer.com Address*: Heidelberg Type:
 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 7965 Number: Month: Pages: 255-266 Year*: 2013 VG Wort Pages: 27 ISBN/ISSN: 978-3-642-39205-4 Sequence Number: DOI: 10.1007/978-3-642-39206-1
 (LaTeX) 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 \le 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 \le q_k \le 2$, we show that $q_k$ can be chosen asymptotically less than $2$. We present algorithms with asymptotic discrepancy $q_k \le 1.59 + o(1)$ valid for all $k$ and $q_k \le \ln(4) + o(1) \le 1.39 + o(1)$ valid for $k$ being a power of two. Experiments indicate the uniform bound $p_k \le 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 \ge 1.30 - o(1)$. We also show that optimal algorithms (yielding the infimum discrepancy) exist for all~$k$. URL for the Abstract: http://arxiv.org/abs/1302.4216 Download Access Level: Internal

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{BringmannDoerrNeumannSliacan2013,
AUTHOR = {Bringmann, Karl and Doerr, Benjamin and Neumann, Adrian and Sliacan, Jakub},
EDITOR = {Fomin, Fedor V. and Freivalds, Rūsiņš and Kwiatkowska, Marta and Peleg, David},
TITLE = {Online Checkpointing with Improved Worst-Case Guarantees},
BOOKTITLE = {Automata, Languages, and Programming - 40th International Colloquium (ICALP 2013)},
PUBLISHER = {Springer},
YEAR = {2013},
ORGANIZATION = {European Association for Theoretical Computer Science (EATCS)},
VOLUME = {7965},
PAGES = {255--266},
SERIES = {Lecture Notes in Computer Science},