Irene Finocchi
Giuseppe F. Italiano
ABSTRACT
We investigate the design of algorithms resilient to memory faults, i. e., algorithms that, despite the corruption of some memory values during their execution, are able to produce a correct output on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(nlog n) comparison-based sorting algorithm can tolerate at most O((nlog n)1/2) memory faults. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((nlog n)1/3) faults. We also prove polylogarithmic lower and upper bounds on fault-tolerant searching.
- A. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974. Google Scholar
Digital Library
- J. A. Aslam and A. Dhagat. Searching in the presence of linearly bounded errors. Proc. 23rd ACM Symp. on Theory of Computing (STOC'91), 486--493, 1991. Google ScholarDigital Library
- S. Assaf and E. Upfal. Fault-tolerant sorting network. Proc. 31st IEEE Symp. on Foundations of Computer Science (FOCS'90), 275--284, 1990.Google ScholarDigital Library
- Y. Aumann and M. A. Bender. Fault-tolerant data structures. Proc. 37th IEEE Symp. on Foundations of Computer Science (FOCS'96), 580--589, 1996. Google ScholarDigital Library
- R. S. Borgstrom and S. Rao Kosaraju. Comparison based search in the presence of errors. Proc. 25th ACM Symp. on Theory of Computing (STOC'93), 130--136, 1993. Google ScholarDigital Library
- P. M. Chen, E. L. Lee, G. A. Gibson, R. H. Katz, and D. A. Patterson. RAID: High-performance, reliable secondary storage. ACM Computing Surveys, 26(2), 145--185, 1994. Google ScholarDigital Library
- B. S. Chlebus, A. Gambin and P. Indyk. PRAM computations resilient to memory faults. Proc. 2nd Annual European Symp. on Algorithms (ESA'94), LNCS 855, 401--412, 1994. Google ScholarDigital Library
- B. S. Chlebus, A. Gambin and P. Indyk. Shared-memory simulations on a faulty-memory DMM. Proc. 23rd International Colloquium on Automata, Languages and Programming (ICALP'96), 586--597, 1996. Google ScholarDigital Library
- B. S. Chlebus, L. Gasieniec and A. Pelc. Fast deterministic simulation of computations on faulty parallel machines. Proc. 3rd Annual European Symp. on Algorithms (ESA'95), LNCS 979, 89--101, 1995. Google ScholarDigital Library
- C. R. Cook and D. J. Kim. Best sorting algorithms for nearly sorted lists. Communications of the ACM, 23, 620--624, 1980. Google ScholarDigital Library
- A. Dhagat, P. Gacs, and P. Winkler. On playing "twenty questions" with a liar. Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms (SODA'92), 16--22, 1992. Google ScholarDigital Library
- M. Farach-Colton. Personal communication. January 2002.Google Scholar
- U. Feige, P. Raghavan, D. Peleg, and E. Upfal. Computing with noisy information. SIAM Journal on Computing, 23, 1001--1018, 1994. Google ScholarDigital Library
- S. Hamdioui, Z. Al-Ars, J. Van de Goor, and M. Rodgers. Dynamic faults in Random-Access-Memories: Concept, faults models and tests. Journal of Electronic Testing: Theory and Applications, 19, 195--205, 2003. Google ScholarDigital Library
- P. Indyk. On word-level parallelism in fault-tolerant computing. Proc. 13th Annual Symp. on Theoretical Aspects of Computer Science (STACS'96), 193--204, 1996. Google ScholarDigital Library
- D. J. Kleitman, A. R. Meyer, R. L. Rivest, J. Spencer, and K. Winklmann. Coping with errors in binary search procedures. Journal of Computer and System Sciences, 20:396--404, 1980.Google ScholarCross Ref
- K. B. Lakshmanan, B. Ravikumar, and K. Ganesan. Coping with erroneous information while sorting. IEEE Trans. on Computers, 40(9):1081--1084, 1991. Google ScholarDigital Library
- T. Leighton and Y. Ma. Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults. SIAM Journal on Computing, 29(1):258--273, 1999. Google ScholarDigital Library
- T. Leighton, Y. Ma and C. G. Plaxton. Breaking the Θ(nlog2 n) barrier for sorting with faults. Journal of Computer and System Sciences, 54:265--304, 1997. Google ScholarDigital Library
- K. Mehlhorn and S. Naher. LEDA: A platform for combinatorial and geometric computing. Cambridge University Press, 1999. Google ScholarDigital Library
- S. Muthukrishnan. On optimal strategies for searching in the presence of errors. Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA'96), 680--689, 1996. Google ScholarDigital Library
- A. Pelc. Searching with known error probability. Theoretical Computer Science, 63, 185--202, 1989. Google ScholarDigital Library
- A. Pelc. Searching games with errors: Fifty years of coping with liars. Theoretical Computer Science, 270, 71--109, 2002. Google ScholarDigital Library
- P. J. Plauger, A. A. Stepanov, M. Lee, D. R. Musser. The C++ Standard Template Library, Prentice Hall, 2000. Google ScholarDigital Library
- B. Ravikumar. A fault-tolerant merge sorting algorithm. Proc. 8th Annual Int. Conf. on Computing and Combinatorics (COCOON'02), LNCS 2387, 440--447, 2002. Google ScholarDigital Library
- A. Renyi. A diary on information theory, J. Wiley and Sons, 1994. Original publication: Naplo az informacioelmeletrol, Gondolat, Budapest, 1976.Google Scholar
- S. M. Ulam. Adventures of a mathematician. Scribners (New York), 1977.Google Scholar
- A. J. Van de Goor. Testing semiconductor memories: Theory and practice, ComTex Publishing, Gouda, The Netherlands, 1998. Google ScholarDigital Library
- A. C. Yao and F. F. Yao. On fault-tolerant networks for sorting. SIAM Journal on Computing, 14, 120--128, 1985.Google ScholarCross Ref
Index Terms
- Sorting and searching in the presence of memory faults (without redundancy)
Recommendations
Optimal resilient sorting and searching in the presence of memory faults
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 ...
Sorting and Searching in Faulty Memories
In this paper we investigate the design and analysis of algorithms resilient to memory faults. We focus on algorithms that, despite the corruption of some memory values during their execution, are nevertheless able to produce a correct output at least ...
The Price of Resiliency: a Case Study on Sorting with Memory Faults
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, ...
Comments