Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:

http://icalp2013.lu.lv/

URL for downloading the paper:

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



Note, Abstract, ©


(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},
ADDRESS = {Riga, Latvia},
ISBN = {978-3-642-39205-4},
DOI = {10.1007/978-3-642-39206-1},
}


Entry last modified by Adrian Neumann, 02/17/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/10/2014 11:16:28 AM
Revision
1.
0.


Editor
Adrian Neumann
Adrian Neumann


Edit Date
10/01/2014 13:25:14
10/01/2014 11:16:28