License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.45
URN: urn:nbn:de:0030-drops-29988
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/2998/
Go to the corresponding LIPIcs Volume Portal

Caminiti, Saverio ; Finocchi, Irene ; Fusco, Emanuele G.

Local dependency dynamic programming in the presence of memory faults

pdf-format:
8.pdf (0.7 MB)

Abstract

We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of faults that may arbitrarily corrupt memory locations during the algorithm execution. As a main result, we devise a general resilient framework that can be applied to all local dependency dynamic programming problems, where updates to entries in the auxiliary table are determined by the contents of neighboring cells. Consider, as an example, the computation of the edit distance between two strings of length n and m. We prove that, for any arbitrarily small constant epsilon in (0,1] and n >=m, this problem can be solved correctly with high probability in O(nm + alpha delta^{1+epsilon}) worst-case time and O(nm + n delta) space, when up to delta memory faults can be inserted by an adversary with unbounded computational power and alpha <= delta is the actual number of faults occurring during the computation. We also show that an optimal edit sequence can be constructed in additional time O(n delta + alpha delta^{1+epsilon}). It follows that our resilient algorithms match the running time and space usage of the standard non-resilient implementations while tolerating almost linearly-many faults.

BibTeX - Entry

@InProceedings{caminiti_et_al:LIPIcs:2011:2998,
  author =	{Saverio Caminiti and Irene Finocchi and Emanuele G. Fusco},
  title =	{{Local dependency dynamic programming in the presence of memory faults}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{45--56},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/2998},
  URN =		{urn:nbn:de:0030-drops-29988},
  doi =		{10.4230/LIPIcs.STACS.2011.45},
  annote =	{Keywords: unreliable memories, fault-tolerant algorithms, local dependency dynamic programming, edit distance}
}

Keywords: unreliable memories, fault-tolerant algorithms, local dependency dynamic programming, edit distance
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI