{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T23:25:04Z","timestamp":1648682704966},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,1,21]],"date-time":"2009-01-21T00:00:00Z","timestamp":1232496000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,4]]},"DOI":"10.1007\/s00453-008-9264-1","type":"journal-article","created":{"date-parts":[[2009,1,20]],"date-time":"2009-01-20T19:55:40Z","timestamp":1232481340000},"page":"597-620","source":"Crossref","is-referenced-by-count":9,"title":["The Price of Resiliency: a Case Study on Sorting with\u00a0Memory Faults"],"prefix":"10.1007","volume":"53","author":[{"given":"Umberto","family":"Ferraro-Petrillo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irene","family":"Finocchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,1,21]]},"reference":[{"key":"9264_CR1","unstructured":"Anderson, R., Kuhn, M.: Tamper resistance\u2014a cautionary note. In: Proc. 2nd Usenix Workshop on Electronic Commerce, pp. 1\u201311 (1996)"},{"key":"9264_CR2","doi-asserted-by":"crossref","unstructured":"Anderson, R., Kuhn, M.: Low cost attacks on tamper resistant devices. In: Proc. International Workshop on Security Protocols, pp. 125\u2013136 (1997)","DOI":"10.1007\/BFb0028165"},{"key":"9264_CR3","doi-asserted-by":"crossref","unstructured":"Aslam, J.A., Dhagat, A.: Searching in the presence of linearly bounded errors. In: Proc. 23rd STOC, pp. 486\u2013493 (1991)","DOI":"10.1145\/103418.103469"},{"issue":"4","key":"9264_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":"9264_CR5","doi-asserted-by":"crossref","unstructured":"Aumann, Y., Bender, M.A.: Fault-tolerant data structures. In: Proc. 37th IEEE Symp. on Foundations of Computer Science (FOCS\u201996), pp. 580\u2013589 (1996)","DOI":"10.1109\/SFCS.1996.548517"},{"key":"9264_CR6","unstructured":"Bentley, J., Sedgewick, R.: Quicksort is optimal. Invited talk at Stanford University, January 2002. Slides available at the URL http:\/\/www.cs.princeton.edu\/~rs\/talks\/QuicksortIsOptimal.pdf"},{"key":"9264_CR7","series-title":"LNCS","first-page":"162","volume-title":"Proc. 7th International Conference on Financial Cryptography (FC\u201903)","author":"J. Bl\u00f6mer","year":"2003","unstructured":"Bl\u00f6mer, J., Seifert, J.-P.: Fault based cryptanalysis of the Advanced Encryption Standard (AES). In: Proc. 7th International Conference on Financial Cryptography (FC\u201903). LNCS, vol. 2742, pp. 162\u2013181. Springer, Berlin (2003)"},{"key":"9264_CR8","doi-asserted-by":"crossref","unstructured":"Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults. In: Proc. EUROCRYPT, pp. 37\u201351 (1997)","DOI":"10.1007\/3-540-69053-0_4"},{"key":"9264_CR9","doi-asserted-by":"crossref","unstructured":"Borgstrom, R.S., Rao Kosaraju, S.: \u00a0Comparison based search in the presence of errors. In: Proc. 25th STOC, pp. 130\u2013136 (1993)","DOI":"10.1145\/167088.167129"},{"key":"9264_CR10","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: Proc. 15th Annual European Symposium on Algorithms (ESA\u201907), pp. 347\u2013358 (2007)","DOI":"10.1007\/978-3-540-75520-3_32"},{"key":"9264_CR11","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., Gambin, A., Indyk, P.: Shared-memory simulations on a faulty-memory DMM. In: Proc. 23rd International Colloquium on Automata, Languages and Programming (ICALP\u201996), pp. 586\u2013597 (1996)","DOI":"10.1007\/3-540-61440-0_161"},{"issue":"3\u20134","key":"9264_CR12","first-page":"285","volume":"55","author":"B.S. Chlebus","year":"2003","unstructured":"Chlebus, B.S., Gasieniec, L., Pelc, A.: Deterministic computations on a PRAM with static processor and memory faults. Fundam. Inform. 55(3\u20134), 285\u2013306 (2003)","journal-title":"Fundam. Inform."},{"key":"9264_CR13","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/359024.359026","volume":"23","author":"C.R. Cook","year":"1980","unstructured":"Cook, C.R., Kim, D.J.: Best sorting algorithms for nearly sorted lists. Commun. ACM 23, 620\u2013624 (1980)","journal-title":"Commun. ACM"},{"key":"9264_CR14","unstructured":"Dhagat, A., Gacs, P., Winkler, P.: On playing \u201ctwenty questions\u201d with a liar. In: Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms (SODA\u201992), pp. 16\u201322 (1992)"},{"key":"9264_CR15","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V. Estivill-Castro","year":"1992","unstructured":"Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Comput. Surv. 24, 441\u2013476 (1992)","journal-title":"ACM Comput. Surv."},{"key":"9264_CR16","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, 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"key":"9264_CR17","doi-asserted-by":"crossref","unstructured":"Ferraro Petrillo, U., Finocchi, I., Italiano, G.F.: The Price of Resiliency: a Case Study on Sorting with Memory Faults. In: Proc. 14th Annual European Symposium on Algorithms (ESA\u201906), pp. 768\u2013779 (2006)","DOI":"10.1007\/11841036_68"},{"issue":"3","key":"9264_CR18","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). Preliminary version in Proc. 36th ACM STOC, pp. 101\u2013110 (2004)","journal-title":"Algorithmica"},{"issue":"2","key":"9264_CR19","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.cosrev.2007.10.001","volume":"1","author":"I. Finocchi","year":"2007","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Designing reliable algorithms in unreliable memories. Comput. Sci. Rev. 1(2), 77\u201387 (2007)","journal-title":"Comput. Sci. Rev."},{"key":"9264_CR20","series-title":"LNCS","first-page":"286","volume-title":"Proc. 33rd ICALP","author":"I. Finocchi","year":"2006","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Optimal sorting and searching in the presence of memory faults. In: Proc. 33rd ICALP. LNCS, vol.\u00a04051, pp. 286\u2013298. Springer, Berlin (2006). To appear in Theor. Comput. Sci."},{"key":"9264_CR21","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Resilient search trees. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907), pp. 547\u2013553 (2007)"},{"key":"9264_CR22","doi-asserted-by":"crossref","unstructured":"Govindavajhala, S., Appel, A.W.: Using memory errors to attack a virtual machine. In: Proc. IEEE Symposium on Security and Privacy, pp. 154\u2013165 (2003)","DOI":"10.1109\/SECPRI.2003.1199334"},{"key":"9264_CR23","doi-asserted-by":"crossref","unstructured":"Henzinger, M.: The past, present and future of web search engines. Invited talk. In: 31st ICALP (2004)","DOI":"10.1007\/978-3-540-27836-8_2"},{"key":"9264_CR24","doi-asserted-by":"crossref","unstructured":"Indyk, P.: On word-level parallelism in fault-tolerant computing. In: Proc. 13th Annual Symp. on Theoretical Aspects of Computer Science (STACS\u201996), pp. 193\u2013204 (1996)","DOI":"10.1007\/3-540-60922-9_17"},{"key":"9264_CR25","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A.G., Moruz, G., M\u00f8lhave, T.: Priority queues resilient to memory faults. In: Proc. 10th Workshop on Algorithms and Data Structures (WADS\u201907), pp. 127\u2013138 (2007)","DOI":"10.1007\/978-3-540-73951-7_12"},{"key":"9264_CR26","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1016\/0022-0000(80)90014-8","volume":"20","author":"D.J. Kleitman","year":"1980","unstructured":"Kleitman, D.J., Meyer, A.R., Rivest, R.L., Spencer, J., Winklmann, K.: Coping with errors in binary search procedures. J. Comput. Syst. Sci. 20, 396\u2013404 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"9264_CR27","unstructured":"Kopetz, H.: Mitigation of transient faults at the system level\u2014the TTA approach. In: Proc. 2nd Workshop on System Effects of Logic Soft Errors (2006)"},{"issue":"9","key":"9264_CR28","doi-asserted-by":"crossref","first-page":"1081","DOI":"10.1109\/12.83656","volume":"40","author":"K.B. Lakshmanan","year":"1991","unstructured":"Lakshmanan, K.B., Ravikumar, B., Ganesan, K.: Coping with erroneous information while sorting. IEEE Trans. Comput. 40(9), 1081\u20131084 (1991)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"9264_CR29","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1137\/S0097539796305298","volume":"29","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., Ma, Y.: Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults. SIAM J. Comput. 29(1), 258\u2013273 (1999)","journal-title":"SIAM J. Comput."},{"key":"9264_CR30","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1006\/jcss.1997.1470","volume":"54","author":"T. Leighton","year":"1997","unstructured":"Leighton, T., Ma, Y., Plaxton, C.G.: Breaking the \u0398(nlog\u20092 n) barrier for sorting with faults. J. Comput. Syst. Sci. 54, 265\u2013304 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9264_CR31","unstructured":"Lu, C., Reed, D.A.: Assessing fault sensitivity in MPI applications. In: Proc. 2004 ACM\/IEEE Conf. on Supercomputing (SC\u201904), p. 37 (2004)"},{"key":"9264_CR32","doi-asserted-by":"crossref","unstructured":"May, T.C., Woods, M.H.: Alpha-particle-induced soft errors in dynamic memories. IEEE Trans. Electron Devices 26(2) (1979)","DOI":"10.1109\/T-ED.1979.19370"},{"key":"9264_CR33","unstructured":"Panzer-Steindel, B.: Data integrity. Available at http:\/\/indico.cern.ch\/getFile.py\/access?contribId=3&sessionId=0&resId=1&materialId=paper&confId=13797 , April 2007"},{"key":"9264_CR34","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0304-3975(89)90077-7","volume":"63","author":"A. Pelc","year":"1989","unstructured":"Pelc, A.: Searching with known error probability. Theor. Comput. Sci. 63, 185\u2013202 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"9264_CR35","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: Fifty years of coping with liars. Theor. Comput. Sci. 270, 71\u2013109 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9264_CR36","unstructured":"Pinheiro, E., Weber, W., Barroso, L.A.: Failure trends in large disk drive populations. In: Proc. 5th USENIX Conference on File and Storage Technologies (2007)"},{"key":"9264_CR37","series-title":"LNCS","first-page":"440","volume-title":"Proc. 8th COCOON","author":"B. Ravikumar","year":"2002","unstructured":"Ravikumar, B.: A fault-tolerant merge sorting algorithm. In: Proc. 8th COCOON. LNCS, vol. 2387, pp. 440\u2013447. Springer, Berlin (2002)"},{"issue":"3","key":"9264_CR38","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/j.future.2004.11.015","volume":"22","author":"D.A. Reed","year":"2006","unstructured":"Reed, D.A., Lu, C., Mendes, C.L.: Reliability challenges in large systems. Future Gener. Comput. Syst. 22(3), 293\u2013302 (2006)","journal-title":"Future Gener. Comput. Syst."},{"issue":"25","key":"9264_CR39","first-page":"1","volume":"7","author":"G.K. Saha","year":"2006","unstructured":"Saha, G.K.: Software based fault tolerance: a survey. Ubiquity 7(25), 1 (2006)","journal-title":"Ubiquity"},{"key":"9264_CR40","series-title":"LNCS","first-page":"2","volume-title":"Proc. 4th International Workshop on Cryptographic Hardware and Embedded Systems (CHES\u201902)","author":"S. Skorobogatov","year":"2002","unstructured":"Skorobogatov, S., Anderson, R.: Optical fault induction attacks. In: Proc. 4th International Workshop on Cryptographic Hardware and Embedded Systems (CHES\u201902). LNCS, vol. 2523, pp. 2\u201312. Springer, Berlin (2002)"},{"key":"9264_CR41","unstructured":"Tezzaron Semiconductor. Soft errors in electronic memory\u2014a white paper. URL: http:\/\/www.tezzaron.com\/about\/papers\/Papers.htm , January 2004"},{"key":"9264_CR42","volume-title":"Testing Semiconductor Memories: Theory and Practice","author":"A.J. Goor Van de","year":"1998","unstructured":"Van de Goor, A.J.: Testing Semiconductor Memories: Theory and Practice. ComTex, Gouda (1998)"},{"key":"9264_CR43","first-page":"43","volume-title":"Automata Studies","author":"J. Neumann Von","year":"1956","unstructured":"Von Neumann, J.: Probabilistic logics and the synthesis of reliable organisms from unreliable components. In: Shannon, C., McCarty, J. (eds.) Automata Studies, pp. 43\u201398. Princeton University Press, Princeton (1956)"},{"key":"9264_CR44","doi-asserted-by":"crossref","unstructured":"Xu, J., Chen, S., Kalbarczyk, Z., Iyer, R.K.: An experimental study of security vulnerabilities caused by errors. In: Proc. International Conference on Dependable Systems and Networks, pp. 421\u2013430 (2001)","DOI":"10.1109\/DSN.2001.941426"},{"key":"9264_CR45","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/0214009","volume":"14","author":"A.C. Yao","year":"1985","unstructured":"Yao, A.C., Yao, F.F.: On fault-tolerant networks for sorting. SIAM J. Comput. 14, 120\u2013128 (1985)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9264-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9264-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9264-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:03Z","timestamp":1559137503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9264-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,21]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["9264"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9264-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,21]]}}}