We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of errors that lead the logical state of some bits to be read differently from how they were last written. Assuming that a limited number of memory faults can be inserted at run-time by an adversary with unbounded computational power, we obtain the first resilient algorithms for a broad range of dynamic programming problems, devising a general framework that can be applied to both iterative and recursive implementations. Besides all local dependency problems, where updates to table entries are determined by the contents of neighboring cells, we also settle challenging non-local problems, such as all-pairs shortest paths and matrix multiplication. All our algorithms are correct with high probability and match the running time of their standard non-resilient counterparts while tolerating a polynomial number of faults. The recursive algorithms are also cache-efficient and can tolerate faults atany level of the memory hierarchy. Our results exploit a careful combination of data replication, majority techniques, fingerprint computations, and lazy fault detection. To cope with the complex data access patterns induced by some of our algorithms, we also devise amplified fingerprints, which might be of independent interest in the design of resilient algorithms for different problems.

Resilient Dynamic Programming / Caminiti, Saverio; Finocchi, Irene; Fusco, EMANUELE GUIDO; Silvestri, Francesco. - In: ALGORITHMICA. - ISSN 0178-4617. - 77:(2017), pp. 389-425. [10.1007/s00453-015-0073-z]

Resilient Dynamic Programming

FINOCCHI, Irene;
2017

Abstract

We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of errors that lead the logical state of some bits to be read differently from how they were last written. Assuming that a limited number of memory faults can be inserted at run-time by an adversary with unbounded computational power, we obtain the first resilient algorithms for a broad range of dynamic programming problems, devising a general framework that can be applied to both iterative and recursive implementations. Besides all local dependency problems, where updates to table entries are determined by the contents of neighboring cells, we also settle challenging non-local problems, such as all-pairs shortest paths and matrix multiplication. All our algorithms are correct with high probability and match the running time of their standard non-resilient counterparts while tolerating a polynomial number of faults. The recursive algorithms are also cache-efficient and can tolerate faults atany level of the memory hierarchy. Our results exploit a careful combination of data replication, majority techniques, fingerprint computations, and lazy fault detection. To cope with the complex data access patterns induced by some of our algorithms, we also devise amplified fingerprints, which might be of independent interest in the design of resilient algorithms for different problems.
Cache-oblivious algorithms; Dynamic programming; Gaussian Elimination Paradigm; Memory faults; Resilient computing; Computer Science (all); Computer Science Applications1707 Computer Vision and Pattern Recognition; Applied Mathematics
Resilient Dynamic Programming / Caminiti, Saverio; Finocchi, Irene; Fusco, EMANUELE GUIDO; Silvestri, Francesco. - In: ALGORITHMICA. - ISSN 0178-4617. - 77:(2017), pp. 389-425. [10.1007/s00453-015-0073-z]
File in questo prodotto:
File Dimensione Formato  
Caminiti_Resilient Dynamic Programming_2015.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 981.42 kB
Formato Adobe PDF
981.42 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/192581
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact