Resilient Dynamic Programming
| Autor: | Francesco Silvestri, Saverio Caminiti, Emanuele G. Fusco, Irene Finocchi |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Theoretical computer science
General Computer Science Computer science 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 0102 computer and information sciences 02 engineering and technology Cache-oblivious algorithm 01 natural sciences Fault detection and isolation 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 0202 electrical engineering electronic engineering information engineering Memory hierarchy Fingerprint (computing) Matrix multiplication Computer Science Applications 010201 computation theory & mathematics Theory of computation 020201 artificial intelligence & image processing State (computer science) Algorithm |
| Popis: | 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 at any 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|