Caminiti, Saverio ;
Finocchi, Irene ;
Fusco, Emanuele G.
Local dependency dynamic programming in the presence of memory faults
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}) worstcase 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 nonresilient implementations while tolerating almost linearlymany 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 = {4556},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/2998},
URN = {urn:nbn:de:0030drops29988},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.45},
annote = {Keywords: unreliable memories, faulttolerant algorithms, local dependency dynamic programming, edit distance}
}
Keywords: 

unreliable memories, faulttolerant algorithms, local dependency dynamic programming, edit distance 
Seminar: 

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Issue date: 

2011 
Date of publication: 

2011 