{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T10:20:41Z","timestamp":1774261241091,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,10,13]],"date-time":"2015-10-13T00:00:00Z","timestamp":1444694400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00453-015-0073-z","type":"journal-article","created":{"date-parts":[[2015,10,14]],"date-time":"2015-10-14T00:38:11Z","timestamp":1444783091000},"page":"389-425","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Resilient Dynamic Programming"],"prefix":"10.1007","volume":"77","author":[{"given":"Saverio","family":"Caminiti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irene","family":"Finocchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele G.","family":"Fusco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Silvestri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,13]]},"reference":[{"issue":"9","key":"73_CR1","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"73_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Feldman, V., Hassidim, A., Nelson, J.: Sorting and selection with imprecise comparisons. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pp. 37\u201348 (2009)","DOI":"10.1007\/978-3-642-02927-1_5"},{"key":"73_CR3","doi-asserted-by":"crossref","unstructured":"Aslam, J.A., Dhagat, A.: Searching in the presence of linearly bounded errors. In: Proceedings of the 23rd ACM Symposium on Theory of Computing, pp. 486\u2013493 (1991)","DOI":"10.1145\/103418.103469"},{"issue":"4","key":"73_CR4","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1137\/0404042","volume":"4","author":"S Assaf","year":"1991","unstructured":"Assaf, S., Upfal, E.: Fault tolerant sorting networks. SIAM J. Discrete Math. 4(4), 472\u2013480 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"73_CR5","doi-asserted-by":"crossref","unstructured":"Aumann, Y., Bender, M.A.: Fault tolerant data structures. In: Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, pp. 580\u2013589 (1996)","DOI":"10.1109\/SFCS.1996.548517"},{"key":"73_CR6","doi-asserted-by":"crossref","unstructured":"Babenko, M.A., Pouzyrevsky, I.: Resilient quicksort and selection. In: Proceedings of the 7th International Computer Science Symposium in Russia. LNCS, vol. 7353, pp. 6\u201317 (2012)","DOI":"10.1007\/978-3-642-30642-6_2"},{"key":"73_CR7","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer, J., Seifert, J.: Fault based cryptanalysis of the advanced encryption standard (AES). In: Financial Cryptography, pp. 162\u2013181 (2003)","DOI":"10.1007\/978-3-540-45126-6_12"},{"issue":"2\u20133","key":"73_CR8","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF01185212","volume":"12","author":"M Blum","year":"1994","unstructured":"Blum, M., Evans, W.S., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. Algorithmica 12(2\u20133), 225\u2013244 (1994)","journal-title":"Algorithmica"},{"key":"73_CR9","doi-asserted-by":"crossref","unstructured":"Borgstrom, R.S., Kosaraju, S.R.: Comparison-based search in the presence of errors. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 130\u2013136 (1993)","DOI":"10.1145\/167088.167129"},{"key":"73_CR10","doi-asserted-by":"crossref","unstructured":"Boyer, R.S., Moore, J.S.: MJRTY: A fast majority vote algorithm. In: Automated Reasoning: Essays in Honor of Woody Bledsoe, pp. 105\u2013118 (1991)","DOI":"10.1007\/978-94-011-3488-0_5"},{"key":"73_CR11","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Finocchi, I., Grandoni, F., Italiano, G.F., J\u00f8rgensen, A.G., Moruz, G., M\u00f8lhave, T.: Optimal resilient dynamic dictionaries. In: Proceedings of the 15th European Symposium on Algorithms. LNCS, vol. 4698, pp. 347\u2013358 (2007)","DOI":"10.7146\/dpb.v36i585.7222"},{"key":"73_CR12","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., J\u00f8rgensen, A.G., M\u00f8lhave, T.: Fault tolerant external memory algorithms. In: Proceedings of the 11th Workshop on Algorithms and Data Structures. LNCS, vol. 5664, pp. 411\u2013422 (2009)","DOI":"10.1007\/978-3-642-03367-4_36"},{"key":"73_CR13","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., J\u00f8rgensen, A.G., Moruz, G., M\u00f8lhave, T.: Counting in the presence of memory faults. In: Proceedings of the 20th International Symposium on Algorithms and Computation. LNCS, vol. 5878, pp. 842\u2013851 (2009)","DOI":"10.1007\/978-3-642-10631-6_85"},{"key":"73_CR14","unstructured":"Caminiti, S., Finocchi, I., Fusco, E.G.: Local dependency dynamic programming in the presence of memory faults. In: Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science. LIPICS, vol. 9, pp. 45\u201356 (2011)"},{"key":"73_CR15","unstructured":"Caminiti, S., Finocchi, I., Fusco, E.G., Silvestri, F.: Dynamic programming in faulty memory hierarchies (cache-obliviously). In: Proceedings of the 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. LIPICS, vol. 13, pp. 433\u2013444 (2011)"},{"issue":"1","key":"73_CR16","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/110834949","volume":"42","author":"V Chen","year":"2013","unstructured":"Chen, V., Grigorescu, E., de Wolf, R.: Error-correcting data structures. SIAM J. Comput. 42(1), 84\u2013111 (2013)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"73_CR17","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1109\/TCBB.2008.94","volume":"7","author":"RA Chowdhury","year":"2010","unstructured":"Chowdhury, R.A., Le, H.S., Ramachandran, V.: Cache-oblivious dynamic programming for bioinformatics. IEEE\/ACM Trans. Comput. Biol. Bioinform. 7(3), 495\u2013510 (2010)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"73_CR18","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-oblivious dynamic programming. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 591\u2013600 (2006)","DOI":"10.1145\/1109557.1109622"},{"key":"73_CR19","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-efficient dynamic programming algorithms for multicores. In: Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 207\u2013216 (2008)","DOI":"10.1145\/1378533.1378574"},{"key":"73_CR20","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1007\/s00224-010-9273-8","volume":"47","author":"RA Chowdhury","year":"2010","unstructured":"Chowdhury, R.A., Ramachandran, V.: The cache-oblivious gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation. Theory Comput. Syst. 47, 878\u2013919 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"7","key":"73_CR21","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1016\/j.jpdc.2013.04.008","volume":"73","author":"RA Chowdhury","year":"2013","unstructured":"Chowdhury, R.A., Ramachandran, V., Silvestri, F., Blakeley, B.: Oblivious algorithms for multicores and networks of processors. J. Parallel Distrib. Comput. 73(7), 911\u2013925 (2013)","journal-title":"J. Parallel Distrib. Comput."},{"key":"73_CR22","doi-asserted-by":"crossref","unstructured":"Christiano, P., Demaine, E.D., Kishore, S.: Lossless fault-tolerant data structures with additive overhead. In: Proceedings of the 14th International Symposium on Algorithms and Data Structures. LNCS, vol. 6844, pp. 243\u2013254 (2011)","DOI":"10.1007\/978-3-642-22300-6_21"},{"key":"73_CR23","doi-asserted-by":"crossref","unstructured":"Chu, M., Kannan, S., McGregor, A.: Checking and spot-checking the correctness of priority queues. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming. LNCS, vol. 4596, pp. 728\u2013739 (2007)","DOI":"10.1007\/978-3-540-73420-8_63"},{"key":"73_CR24","doi-asserted-by":"crossref","unstructured":"De Stefani, L., Silvestri, F.: Exploiting non-constant safe memory in resilient algorithms and data structures. Theor. Comput. Sci. 583, 86\u201397 (2015)","DOI":"10.1016\/j.tcs.2015.04.003"},{"issue":"5","key":"73_CR25","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"73_CR26","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/s00453-008-9264-1","volume":"53","author":"U Ferraro Petrillo","year":"2009","unstructured":"Ferraro Petrillo, U., Finocchi, I., Italiano, G\u00a0.F.: The price of resiliency: a case study on sorting with memory faults. Algorithmica 53(4), 597\u2013620 (2009)","journal-title":"Algorithmica"},{"key":"73_CR27","doi-asserted-by":"crossref","first-page":"1.6:1.1","DOI":"10.1145\/2444016.2444022","volume":"18","author":"U Ferraro Petrillo","year":"2013","unstructured":"Ferraro Petrillo, U., Grandoni, F., Italiano, G.F.: Data structures resilient to memory faults: an experimental study of dictionaries. ACM J. Exp. Algorithmics 18, 1.6:1.1\u20131.6:1.14 (2013)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"44","key":"73_CR28","doi-asserted-by":"crossref","first-page":"4457","DOI":"10.1016\/j.tcs.2009.07.026","volume":"410","author":"I Finocchi","year":"2009","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Optimal resilient sorting and searching in the presence of memory faults. Theor. Comput. Sci. 410(44), 4457\u20134470 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"73_CR29","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/1644015.1644016","volume":"6","author":"I Finocchi","year":"2009","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Resilient dictionaries. ACM Trans. Algorithms 6(1), 1:1\u20131:19 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"73_CR30","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s00453-007-9088-4","volume":"52","author":"I Finocchi","year":"2008","unstructured":"Finocchi, I., Italiano, G.F.: Sorting and searching in faulty memories. Algorithmica 52(3), 309\u2013332 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"73_CR31","doi-asserted-by":"crossref","first-page":"4:1","DOI":"10.1145\/2071379.2071383","volume":"8","author":"M Frigo","year":"2012","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. ACM Trans. Algorithms 8(1), 4:1\u20134:22 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"73_CR32","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/s11704-012-2870-8","volume":"6","author":"F Gieseke","year":"2012","unstructured":"Gieseke, F., Moruz, G., Vahrenhold, J.: Resilient k-d trees: k-means in space revisited. Front. Comput. Sci. 6(2), 166\u2013178 (2012)","journal-title":"Front. Comput. Sci."},{"key":"73_CR33","doi-asserted-by":"crossref","unstructured":"Govindavajhala, S., Appel, A.W.: Using memory errors to attack a virtual machine. In: IEEE Symposium on Security and Privacy, pp. 154\u2013165 (2003)","DOI":"10.1109\/SECPRI.2003.1199334"},{"key":"73_CR34","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"73_CR35","volume-title":"Memory Systems: Cache, DRAM, Disk","author":"BL Jacob","year":"2008","unstructured":"Jacob, B.L., Ng, S.W., Wang, D.T.: Memory Systems: Cache, DRAM, Disk. Morgan Kaufmann, Burlington (2008)"},{"key":"73_CR36","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A.G., Moruz, G., M\u00f8lhave, T.: Priority queues resilient to memory faults. In: Proceedings of the 10th Workshop on Algorithms and Data Structures. LNCS, vol. 4619, pp. 127\u2013138 (2007)","DOI":"10.1007\/978-3-540-73951-7_12"},{"issue":"2","key":"73_CR37","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"73_CR38","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Talmon, N.: Selection in the presence of memory faults, with applications to in-place resilient sorting. In: Proceedings of the 23rd International Symposium on Algorithms and Computation. LNCS, vol. 7676, pp. 558\u2013567 (2012)","DOI":"10.1007\/978-3-642-35261-4_58"},{"issue":"2","key":"73_CR39","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1006\/jcss.1997.1470","volume":"54","author":"FT Leighton","year":"1997","unstructured":"Leighton, F.T., Ma, Y., Plaxton, C.G.: Breaking the $$\\Theta (n \\log ^2 n)$$ \u0398 ( n log 2 n ) barrier for sorting with faults. J. Comput. Syst. Sci. 54(2), 265\u2013304 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"73_CR40","doi-asserted-by":"crossref","unstructured":"Li, D., Chen, Z., Wu, P., Vetter, J.S.: Rethinking algorithm-based fault tolerance with a cooperative software\u2013hardware approach. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, pp. 44:1\u201344:12 (2013)","DOI":"10.1145\/2503210.2503226"},{"key":"73_CR41","unstructured":"Muthukrishnan, S.: On optimal strategies for searching in presence of errors. In: Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, pp. 680\u2013689 (1994)"},{"issue":"1\u20132","key":"73_CR42","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0304-3975(01)00303-6","volume":"270","author":"A Pelc","year":"2002","unstructured":"Pelc, A.: Searching games with errors\u2014fifty years of coping with liars. Theor. Comput. Sci. 270(1\u20132), 71\u2013109 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"73_CR43","doi-asserted-by":"crossref","first-page":"1874","DOI":"10.1109\/TNS.2014.2301768","volume":"61","author":"LL Pilla","year":"2014","unstructured":"Pilla, L.L., Rech, P., Silvestri, F., Frost, C., Navaux, P.O.A., Sonza, M., Carro, L.: Software-based hardening strategies for neutron sensitive FFT algorithms on GPUs. IEEE Trans. Nucl. Sci. 61(4), 1874\u20131880 (2014)","journal-title":"IEEE Trans. Nucl. Sci."},{"issue":"1","key":"73_CR44","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"MO Rabin","year":"1980","unstructured":"Rabin, M.O.: Probabilistic algorithm for testing primality. J. Number Theory 12(1), 128\u2013138 (1980)","journal-title":"J. Number Theory"},{"key":"73_CR45","doi-asserted-by":"crossref","unstructured":"Rech, P., Pilla, L., Silvestri, F., Navaux, P., Carro, L.: Neutron sensitivity and software hardening strategies for matrix multiplication and FFT on graphics processing units. In: Proceedings of the 3rd Workshop on Fault-tolerance for HPC at Extreme Scale, pp. 13\u201320 (2013)","DOI":"10.1145\/2465813.2465816"},{"issue":"2","key":"73_CR46","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1145\/1897816.1897844","volume":"54","author":"B Schroeder","year":"2011","unstructured":"Schroeder, B., Pinheiro, E., Weber, W.D.: DRAM errors in the wild: a large-scale field study. Commun. ACM 54(2), 100\u2013107 (2011)","journal-title":"Commun. ACM"},{"key":"73_CR47","volume-title":"Algorithms and Data Structures for External Memory","author":"JS Vitter","year":"2008","unstructured":"Vitter, J.S.: Algorithms and Data Structures for External Memory. Now Publishers Inc., Hanover (2008)"},{"key":"73_CR48","unstructured":"Ward, M.: Mistakes in silicon chips to help boost computer power. BBC News (May 25, 2010). http:\/\/news.bbc.co.uk\/2\/hi\/technology\/10134655.stm"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0073-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0073-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0073-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0073-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T04:15:35Z","timestamp":1653279335000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0073-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,13]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["73"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0073-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,13]]}}}