{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T02:46:55Z","timestamp":1768704415722,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T00:00:00Z","timestamp":1193443200000},"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":[[2008,11]]},"DOI":"10.1007\/s00453-007-9088-4","type":"journal-article","created":{"date-parts":[[2007,10,26]],"date-time":"2007-10-26T12:06:58Z","timestamp":1193400418000},"page":"309-332","source":"Crossref","is-referenced-by-count":31,"title":["Sorting and Searching in Faulty Memories"],"prefix":"10.1007","volume":"52","author":[{"given":"Irene","family":"Finocchi","sequence":"first","affiliation":[]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,27]]},"reference":[{"key":"9088_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1974","unstructured":"Aho, A., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison\u2013Wesley, Reading (1974)"},{"key":"9088_CR2","unstructured":"Aslam, J.A., Dhagat, A.: Searching in the presence of linearly bounded errors. In: Proc. 23rd ACM Symp. on Theory of Computing (STOC\u201991), pp. 486\u2013493, 1991"},{"issue":"4","key":"9088_CR3","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":"9088_CR4","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":"9088_CR5","unstructured":"Bl\u00f6mer, J., Seifert, J.-P.: Fault based cryptanalysis of the advanced encryption standard (AES). In:\u00a0Proc. 7th International Conference on Financial Cryptography (FC\u201903). LNCS vol. 2742, pp. 162\u2013181, 2003"},{"key":"9088_CR6","doi-asserted-by":"crossref","unstructured":"Borgstrom, R.S., Rao Kosaraju, S.: Comparison based search in the presence of errors. In: Proc. 25th\u00a0ACM Symp. on Theory of Computing (STOC\u201993), pp. 130\u2013136, 1993","DOI":"10.1145\/167088.167129"},{"issue":"2","key":"9088_CR7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1145\/176979.176981","volume":"26","author":"P.M. Chen","year":"1994","unstructured":"Chen, P.M., Lee, E.L., Gibson, G.A., Katz, R.H., Patterson, D.A.: RAID: high-performance, reliable secondary storage. ACM Comput. Surv. 26(2), 145\u2013185 (1994)","journal-title":"ACM Comput. Surv."},{"key":"9088_CR8","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., Gambin, A., Indyk, P.: PRAM computations resilient to memory faults. In: Proc. 2nd\u00a0Annual European Symp. on Algorithms (ESA\u201994). LNCS vol. 855, pp. 401\u2013412, 1994","DOI":"10.1007\/BFb0049426"},{"key":"9088_CR9","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.\u00a0586\u2013597, 1996","DOI":"10.1007\/3-540-61440-0_161"},{"issue":"3\u20134","key":"9088_CR10","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":"9088_CR11","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":"9088_CR12","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":"9088_CR13","unstructured":"Farach-Colton, M.: Personal communication (January 2002)"},{"key":"9088_CR14","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":"9088_CR15","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.\u00a0768\u2013779, 2006","DOI":"10.1007\/11841036_68"},{"key":"9088_CR16","doi-asserted-by":"crossref","unstructured":"Finocchi, I., Italiano, G.F.: Sorting and searching in the presence of memory faults (without redundancy). In: Proc. 36th ACM Symposium on Theory of Computing (STOC\u201904), pp. 101\u2013110, 2004","DOI":"10.1145\/1007352.1007375"},{"key":"9088_CR17","doi-asserted-by":"crossref","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Optimal sorting and searching in the presence of memory faults. In: Proc. 33rd ICALP. LNCS vol. 4051, pp. 286\u2013298, 2006","DOI":"10.1007\/11786986_26"},{"key":"9088_CR18","unstructured":"Finocchi, I., Grandoni, F., Italiano, G.F.: Resilient search trees. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02007), pp.\u00a0547\u2013553, 2007"},{"key":"9088_CR19","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1023\/A:1022802010738","volume":"19","author":"S. Hamdioui","year":"2003","unstructured":"Hamdioui, S., Al-Ars, Z., Van de Goor, J., Rodgers, M.: Dynamic faults in random-access-memories: concept, faults models and tests. J. Electron. Test. Theory Appl. 19, 195\u2013205 (2003)","journal-title":"J. Electron. Test. Theory Appl."},{"key":"9088_CR20","doi-asserted-by":"crossref","unstructured":"Henzinger, M.: The past, present and future of web search engines. Invited talk. In: 1st Int. Coll. Automata, Languages and Programming, Turku, Finland, 12\u201316 July 2004","DOI":"10.1007\/978-3-540-27836-8_2"},{"key":"9088_CR21","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.\u00a0193\u2013204, 1996","DOI":"10.1007\/3-540-60922-9_17"},{"key":"9088_CR22","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."},{"issue":"9","key":"9088_CR23","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":"9088_CR24","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":"9088_CR25","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":"9088_CR26","doi-asserted-by":"crossref","unstructured":"May, T.C., Woods, M.H.: Alpha-particle-induced soft errors in dynamic memories. IEEE Trans. Elect. Dev. 26(2) (1979)","DOI":"10.1109\/T-ED.1979.19370"},{"key":"9088_CR27","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)"},{"key":"9088_CR28","unstructured":"Muthukrishnan, S.: On optimal strategies for searching in the presence of errors. In: Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA\u201994), pp.\u00a0680\u2013689, 1994"},{"key":"9088_CR29","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":"9088_CR30","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":"9088_CR31","volume-title":"The C++ Standard Template Library","author":"P.J. Plauger","year":"2000","unstructured":"Plauger, P.J., Stepanov, A.A., Lee, M., Musser, D.R.: The C++ Standard Template Library. Prentice Hall, New York (2000)"},{"key":"9088_CR32","unstructured":"Quisquater, J.J., Samyde, D.: Eddy current for magnetic analysis with active sensor. In: Proc. International Conference on Research in SmartCards (E-Smart\u201902), pp.\u00a0185\u2013194, 2002"},{"key":"9088_CR33","doi-asserted-by":"crossref","unstructured":"Ravikumar, B.: A fault-tolerant merge sorting algorithm. In: Proc. 8th Annual Int. Conf. on Computing and Combinatorics (COCOON\u201902). LNCS vol. 2387, pp.\u00a0440\u2013447, 2002","DOI":"10.1007\/3-540-45655-4_47"},{"key":"9088_CR34","volume-title":"A Diary on Information Theory","author":"A. R\u00e9nyi","year":"1994","unstructured":"R\u00e9nyi, A.: A Diary on Information Theory. Wiley, New York (1994) Original publication: Napl\u00f3 az Inform\u00e1ci\u00f3elm\u00e9letr\u00f6l. Gondolat, Budapest (1976)"},{"key":"9088_CR35","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, 2002"},{"key":"9088_CR36","unstructured":"Tezzaron Semiconductor. Soft errors in electronic memory\u2014a white paper, URL: http:\/\/www.tezzaron.com\/about\/papers\/Papers.htm , January 2004"},{"key":"9088_CR37","volume-title":"Adventures of a Mathematician","author":"S.M. Ulam","year":"1977","unstructured":"Ulam, S.M.: Adventures of a Mathematician. Scribners, New York (1977)"},{"key":"9088_CR38","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 Publishing, Gouda (1998)"},{"key":"9088_CR39","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-007-9088-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9088-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9088-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:00Z","timestamp":1559123100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9088-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,27]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["9088"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9088-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,27]]}}}