Authors : Umberto Ferraro-Petrillo , Fabrizio Grandoni , Giuseppe F. Italiano Authors Info & Claims
Article No.: 1.6, Pages 1.1 - 1.14 Published : 19 April 2013 Publication History 7 citation 379 Downloads Total Citations 7 Total Downloads 379 Last 12 Months 3 Last 6 weeks 0 Get Citation AlertsThis alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
We address the problem of implementing data structures resilient to memory faults, which may arbitrarily corrupt memory locations. In this framework, we focus on the implementation of dictionaries and perform a thorough experimental study using a testbed that we designed for this purpose. Our main discovery is that the best-known (asymptotically optimal) resilient data structures have very large space overheads. More precisely, most of the space used by these data structures is not due to key storage. This might not be acceptable in practice, since resilient data structures are meant for applications where a huge amount of data (often of the order of terabytes) has to be stored. Exploiting techniques developed in the context of resilient (static) sorting and searching, in combination with some new ideas, we designed and engineered an alternative implementation, which, while still guaranteeing optimal asymptotic time and space bounds, performs much better in terms of memory without compromising the time efficiency.
Aslam, J. A. and Dhagat, A. 1991. Searching in the presence of linearly bounded errors. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC'91). ACM, New York, 486--493.
Assaf, S. and Upfal, E. 1991. Fault tolerant sorting networks. SIAM J. Discret. Math. 4, 4, 472--480.
Aumann, Y. and Bender, M. A. 1996. Fault tolerant data structures. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS'96). IEEE Computer Society, Los Alamitos, CA, USA, 580--.
Borgstrom, R. S. and Kosaraju, S. R. 1993. Comparison-based search in the presence of errors. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC'93). ACM, New York, 130--136.
Boyer, R. S. and Moore, J. S. 1982. MJRTY—a fast majority vote algorithm. http://www.cs.utexas.edu/ftp/techreports/tr81-32.pdf.
Brodal, G. S., Fagerberg, R., Finocchi, I., Grandoni, F., Italiano, G. F., Jørgensen, A. G., Moruz, G., and Mølhave, T. 2007. Optimal resilient dynamic dictionaries. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA'07). Springer-Verlag, Berlin, 347--358.
Chlebus, B. S., Gambin, A., and Indyk, P. 1996. Shared-memory simulations on a faulty-memory DMM. In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96). Springer-Verlag, Berlin, 586--597.
Feige, U., Raghavan, P., Peleg, D., and Upfal, E. 1994. Computing with noisy information. SIAM J. Comput. 23, 5, 1001--1018.
Ferraro-Petrillo, U., Finocchi, I., and Italiano, G. F. 2006. The price of resiliency: A case study on sorting with memory faults. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA'06). Springer, Berlin, 768--779.
Ferraro-Petrillo, U., Finocchi, I., and Italiano, G. F. 2009. The price of resiliency: A case study on sorting with memory faults. Algorithmica 53, 4, 597--620.
Ferraro-Petrillo, U., Finocchi, I., and Italiano, G. F. 2010a. Experimental study of resilient algorithms and data structures. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10). Springer, Berlin, 1--12.
Ferraro-Petrillo, U., Grandoni, F., and Italiano, G. F. 2010b. Data structures resilient to memory faults: An experimental study of dictionaries. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10). Springer, Berlin, 398--410.
Finocchi, I., Grandoni, F., and Italiano, G. F. 2005. Designing reliable algorithms in unreliable memories. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05). Springer-Verlag, Berlin, 1--8.
Finocchi, I., Grandoni, F., and Italiano, G. F. 2007. Resilient search trees. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). SIAM, Philadelphia, 547--553.
Finocchi, I., Grandoni, F., and Italiano, G. F. 2009. Optimal resilient sorting and searching in the presence of memory faults. Theor. Comput. Sci. 410, 44, 4457--4470.
Finocchi, I. and Italiano, G. F. 2008. Sorting and searching in faulty memories. Algorithmica 52, 3, 309--332.
Hamdioui, S., Al-Ars, Z., Van De Goor, A. J., and Rodgers, M. 2003. Dynamic faults in random-access-memories: Concept, fault models and tests. J. Electron. Test. 19, 2, 195--205.
Henzinger, M. 2004. The past, present and future of web search engines (invited talk). In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04). Springer.
Henzinger, M. 2007. Combinatorial algorithms for web search engines: Three success stories. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). SIAM, Philadelphia, 1022--1026.
Leighton, T. and Ma, Y. 1999. Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults. SIAM J. Comput. 29, 1, 258--273.
May, T. and Woods, M. 1979. Alpha-particle-induced soft errors in dynamic memories. IEEE Trans. Electron Devices 26, 1, 2--9.
Pelc, A. 2002. Searching games with errors—fifty years of coping with liars. Theor. Comput. Sci. 270, 1-2, 71--109.
Rivest, R. L., Meyer, A. R., and Kleitman, D. J. 1978. Coping with errors in binary search procedures (preliminary report). In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC'78). ACM, New York, 227--232.
Schroeder, B., Pinheiro, E., and Weber, W.-D. 2009. Dram errors in the wild: A large-scale field study. In Proceedings of the 11th International Joint Conference on Measurement and Modeling of Computer Systems (SIGMETRICS'09). ACM, New York, 193--204.
Tezzaron Semiconductor. 2004. Soft Errors in electronic memory—A white paper. Tech. rep. http://www. tezzaron.com/about/papers/soft_errors_1_1_secure.pdf.
Yao, A. and Yao, F. 1985. On fault-tolerant networks for sorting. SIAM J. Comput. 14, 1, 120--128.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 investigate the problem of reliable computation in the presence of faults that may arbitrarily corrupt memory locations. In this framework, we consider the problems of sorting and searching in optimal time while tolerating the largest possible number .
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, .
Reviewer: Paparao S Kavalipati
Soft errors in electronics equipment can be caused by alpha particles or noise, and can change data that is being processed. The chance of these errors occuring increases with the size and speed of the memory used by the component. Memory cells can also be modified by optical and electromagnetic attacks aimed at determining secret keys used in encryption. It is necessary to develop techniques that make computations reliable in the presence of memory faults. Introducing error correction circuitry to address the problem increases costs in terms of both money and performance. Another solution is to replicate the data, but that is not practical in situations where the objects to be managed are complex. There is motivation to develop algorithms that can be resilient to memory faults. Such algorithms need to produce the correct output at least for the set of uncorrupted values. In an earlier work, some of the authors of this paper introduced a model for a faulty random access machine (RAM) in which an adversary can corrupt a certain number of words (with an upper bound) while a constant set of words remains safe, and the algorithms can choose to load certain RAM words in safe memory. In this paper, the authors consider resilient data structures, especially the implementation of dictionaries with a resilient search operation. They model the data structure and the adversary as two separate parallel threads, with the first running the input sequence of operations and the second injecting faults by selecting an unsafe memory word at random. This paper is mostly an experimental study, but the background material is covered in detail and provides sufficient information for someone new to the domain. After analyzing the comparative performance of earlier known data structures, the authors observe their large overhead in space, which motivates the development of a variant dictionary called RandMem that makes use of a secondary buffer. Insight for the improvement is derived by optimizing the implementation of an earlier dictionary called Rand. These results and the material presented here will be more interesting to practitioners who work with terabytes of inexpensive storage. As shown in the paper, it is not the actual number of faults, but rather the upper bound on their estimate that has the greater impact on running time. Though that is useful information, further research is necessary to determine how implementations can select such parameters. Online Computing Reviews Service
Become a reviewer for Computing Reviews.
