×

zbMATH — the first resource for mathematics

The price of resiliency: a case study on sorting with memory faults. (English) Zbl 1183.68229
Summary: We address the problem of sorting in the presence of faults that may arbitrarily corrupt memory locations, and investigate the impact of memory faults both on the correctness and on the running times of mergesort-based algorithms. To achieve this goal, we develop a software testbed that simulates different fault injection strategies, and perform a thorough experimental study using a combination of several fault parameters. Our experiments give evidence that simple-minded approaches to this problem are largely impractical, while the design of more sophisticated resilient algorithms seems really worth the effort. Another contribution of our computational study is a carefully engineered implementation of a resilient sorting algorithm, which appears robust to different memory fault patterns.
Reviewer: Reviewer (Berlin)

MSC:
68P10 Searching and sorting
Software:
CONFID
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anderson, R., Kuhn, M.: Tamper resistance–a cautionary note. In: Proc. 2nd Usenix Workshop on Electronic Commerce, pp. 1–11 (1996)
[2] Anderson, R., Kuhn, M.: Low cost attacks on tamper resistant devices. In: Proc. International Workshop on Security Protocols, pp. 125–136 (1997) · Zbl 0895.68040
[3] Aslam, J.A., Dhagat, A.: Searching in the presence of linearly bounded errors. In: Proc. 23rd STOC, pp. 486–493 (1991)
[4] Assaf, S., Upfal, E.: Fault-tolerant sorting networks. SIAM J. Discrete Math. 4(4), 472–480 (1991) · Zbl 0735.68019 · doi:10.1137/0404042
[5] Aumann, Y., Bender, M.A.: Fault-tolerant data structures. In: Proc. 37th IEEE Symp. on Foundations of Computer Science (FOCS’96), pp. 580–589 (1996)
[6] Bentley, J., Sedgewick, R.: Quicksort is optimal. Invited talk at Stanford University, January 2002. Slides available at the URL http://www.cs.princeton.edu/\(\sim\)rs/talks/QuicksortIsOptimal.pdf
[7] Blömer, J., Seifert, J.-P.: Fault based cryptanalysis of the Advanced Encryption Standard (AES). In: Proc. 7th International Conference on Financial Cryptography (FC’03). LNCS, vol. 2742, pp. 162–181. Springer, Berlin (2003) · Zbl 1274.94043
[8] Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults. In: Proc. EUROCRYPT, pp. 37–51 (1997)
[9] Borgstrom, R.S., Rao Kosaraju, S.: Comparison based search in the presence of errors. In: Proc. 25th STOC, pp. 130–136 (1993) · Zbl 1310.68070
[10] Brodal, G.S., Fagerberg, R., Finocchi, I., Grandoni, F., Italiano, G.F., Jørgensen, A.G., Moruz, G., Mølhave, T.: Optimal resilient dynamic dictionaries. In: Proc. 15th Annual European Symposium on Algorithms (ESA’07), pp. 347–358 (2007) · Zbl 1151.68384
[11] 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’96), pp. 586–597 (1996) · Zbl 1046.68533
[12] Chlebus, B.S., Gasieniec, L., Pelc, A.: Deterministic computations on a PRAM with static processor and memory faults. Fundam. Inform. 55(3–4), 285–306 (2003) · Zbl 1030.68048
[13] Cook, C.R., Kim, D.J.: Best sorting algorithms for nearly sorted lists. Commun. ACM 23, 620–624 (1980) · doi:10.1145/359024.359026
[14] Dhagat, A., Gacs, P., Winkler, P.: On playing ”twenty questions” with a liar. In: Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms (SODA’92), pp. 16–22 (1992) · Zbl 0818.90138
[15] Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Comput. Surv. 24, 441–476 (1992) · doi:10.1145/146370.146381
[16] Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23, 1001–1018 (1994) · Zbl 0813.68057 · doi:10.1137/S0097539791195877
[17] 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’06), pp. 768–779 (2006) · Zbl 1131.68434
[18] Finocchi, I., Italiano, G.F.: Sorting and searching in faulty memories. Algorithmica 52(3), 309–332 (2008). Preliminary version in Proc. 36th ACM STOC, pp. 101–110 (2004) · Zbl 1163.68319 · doi:10.1007/s00453-007-9088-4
[19] Finocchi, I., Grandoni, F., Italiano, G.F.: Designing reliable algorithms in unreliable memories. Comput. Sci. Rev. 1(2), 77–87 (2007) · Zbl 1302.68106 · doi:10.1016/j.cosrev.2007.10.001
[20] 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–298. Springer, Berlin (2006). To appear in Theor. Comput. Sci. · Zbl 1223.68033
[21] Finocchi, I., Grandoni, F., Italiano, G.F.: Resilient search trees. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA’07), pp. 547–553 (2007) · Zbl 1302.68099
[22] Govindavajhala, S., Appel, A.W.: Using memory errors to attack a virtual machine. In: Proc. IEEE Symposium on Security and Privacy, pp. 154–165 (2003)
[23] Henzinger, M.: The past, present and future of web search engines. Invited talk. In: 31st ICALP (2004) · Zbl 1098.68520
[24] Indyk, P.: On word-level parallelism in fault-tolerant computing. In: Proc. 13th Annual Symp. on Theoretical Aspects of Computer Science (STACS’96), pp. 193–204 (1996) · Zbl 1379.68132
[25] Jørgensen, A.G., Moruz, G., Mølhave, T.: Priority queues resilient to memory faults. In: Proc. 10th Workshop on Algorithms and Data Structures (WADS’07), pp. 127–138 (2007) · Zbl 1209.68159
[26] 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–404 (1980) · Zbl 0443.68043 · doi:10.1016/0022-0000(80)90014-8
[27] Kopetz, H.: Mitigation of transient faults at the system level–the TTA approach. In: Proc. 2nd Workshop on System Effects of Logic Soft Errors (2006)
[28] Lakshmanan, K.B., Ravikumar, B., Ganesan, K.: Coping with erroneous information while sorting. IEEE Trans. Comput. 40(9), 1081–1084 (1991) · Zbl 05105571 · doi:10.1109/12.83656
[29] 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–273 (1999) · Zbl 0937.68159 · doi:10.1137/S0097539796305298
[30] Leighton, T., Ma, Y., Plaxton, C.G.: Breaking the \(\Theta\)(nlog 2 n) barrier for sorting with faults. J. Comput. Syst. Sci. 54, 265–304 (1997) · Zbl 0872.68033 · doi:10.1006/jcss.1997.1470
[31] Lu, C., Reed, D.A.: Assessing fault sensitivity in MPI applications. In: Proc. 2004 ACM/IEEE Conf. on Supercomputing (SC’04), p. 37 (2004)
[32] May, T.C., Woods, M.H.: Alpha-particle-induced soft errors in dynamic memories. IEEE Trans. Electron Devices 26(2) (1979)
[33] 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
[34] Pelc, A.: Searching with known error probability. Theor. Comput. Sci. 63, 185–202 (1989) · Zbl 0664.68062 · doi:10.1016/0304-3975(89)90077-7
[35] Pelc, A.: Searching games with errors: Fifty years of coping with liars. Theor. Comput. Sci. 270, 71–109 (2002) · Zbl 0984.68041 · doi:10.1016/S0304-3975(01)00303-6
[36] 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)
[37] Ravikumar, B.: A fault-tolerant merge sorting algorithm. In: Proc. 8th COCOON. LNCS, vol. 2387, pp. 440–447. Springer, Berlin (2002) · Zbl 1077.68624
[38] Reed, D.A., Lu, C., Mendes, C.L.: Reliability challenges in large systems. Future Gener. Comput. Syst. 22(3), 293–302 (2006) · doi:10.1016/j.future.2004.11.015
[39] Saha, G.K.: Software based fault tolerance: a survey. Ubiquity 7(25), 1 (2006) · Zbl 1103.68027
[40] Skorobogatov, S., Anderson, R.: Optical fault induction attacks. In: Proc. 4th International Workshop on Cryptographic Hardware and Embedded Systems (CHES’02). LNCS, vol. 2523, pp. 2–12. Springer, Berlin (2002) · Zbl 1019.68581
[41] Tezzaron Semiconductor. Soft errors in electronic memory–a white paper. URL: http://www.tezzaron.com/about/papers/Papers.htm , January 2004
[42] Van de Goor, A.J.: Testing Semiconductor Memories: Theory and Practice. ComTex, Gouda (1998)
[43] Von Neumann, J.: Probabilistic logics and the synthesis of reliable organisms from unreliable components. In: Shannon, C., McCarty, J. (eds.) Automata Studies, pp. 43–98. Princeton University Press, Princeton (1956)
[44] 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–430 (2001)
[45] Yao, A.C., Yao, F.F.: On fault-tolerant networks for sorting. SIAM J. Comput. 14, 120–128 (1985) · Zbl 0557.68042 · doi:10.1137/0214009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.