Sorting and searching in the presence of memory faults (without redundancy)

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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Javed A. Aslam , Aditi Dhagat, Searching in the presence of linearly bounded errors, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.486-493, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103469]
• 3: S. Assaf and E. Upfal. Fault-tolerant sorting network. Proc. 31st IEEE Symp. on Foundations of Computer Science (FOCS'90), 275--284, 1990.
• 4: Y. Aumann , M. A. Bender, Fault tolerant data structures, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.580, October 14-16, 1996
• 5: Ryan S. Borgstrom , S. Rao Kosaraju, Comparison-based search in the presence of errors, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.130-136, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167129]
• 6: Peter M. Chen , Edward K. Lee , Garth A. Gibson , Randy H. Katz , David A. Patterson, RAID: high-performance, reliable secondary storage, ACM Computing Surveys (CSUR), v.26 n.2, p.145-185, June 1994 [doi>10.1145/176979.176981]
• 7: Bogdan S. Chlebus , Anna Gambin , Piotr Indyk, PRAM Computations Resilient to Memory Faults, Proceedings of the Second Annual European Symposium on Algorithms, p.401-412, September 26-28, 1994
• 8: Bogdan S. Chlebus , Anna Gambin , Piotr Indyk, Shared-Memory Simulations on a Faulty-Memory DMM, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.586-597, July 08-12, 1996
• 9: Bogdan S. Chlebus , Leszek Gasieniec , Andrzej Pelc, Fast Deterministic Simulation of Computations on Faulty Parallel Machines, Proceedings of the Third Annual European Symposium on Algorithms, p.89-101, September 25-27, 1995
• 10: Curtis R. Cook , Do Jin Kim, Best sorting algorithm for nearly sorted lists, Communications of the ACM, v.23 n.11, p.620-624, Nov. 1980 [doi>10.1145/359024.359026]
• 11: Aditi Dhagat , Peter Gács , Peter Winkler, On playing “Twenty Questions” with a liar, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.16-22, September 1992, Orlando, Florida, United States
• 12: M. Farach-Colton. Personal communication. January 2002.
• 13: Uriel Feige , Prabhakar Raghavan , David Peleg , Eli Upfal, Computing with Noisy Information, SIAM Journal on Computing, v.23 n.5, p.1001-1018, Oct. 1994 [doi>10.1137/S0097539791195877]
• 14: Said Hamdioui , Zaid Al-Ars , Ad J. Van De Goor , Mike Rodgers, Dynamic Faults in Random-Access-Memories: Concept, Fault Models and Tests, Journal of Electronic Testing: Theory and Applications, v.19 n.2, p.195-205, April 2003 [doi>10.1023/A:1022802010738]
• 15: Piotr Indyk, On Word-Level Parallelism in Fault-Tolerant Computing, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.193-204, February 22-24, 1996
• 16: 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.
• 17: K. B. Lakshmanan , B. Ravikumar , K. Ganesan, Coping with Erroneous Information While Sorting, IEEE Transactions on Computers, v.40 n.9, p.1081-1084, September 1991 [doi>10.1109/12.83656]
• 18: Tom Leighton , Yuan Ma, Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults, SIAM Journal on Computing, v.29 n.1, p.258-273, Feb. 2000 [doi>10.1137/S0097539796305298]
• 19: Tom Leighton , Yuan Ma , C. Greg Plaxton, Breaking the &thgr;(nlog2n) barrier for sorting with faults, Journal of Computer and System Sciences, v.54 n.2, p.265-304, April 1997 [doi>10.1006/jcss.1997.1470]
• 20: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 21: S. Muthukrishnan, On optimal strategies for searching in presence of errors, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.680-689, January 23-25, 1994, Arlington, Virginia, United States
• 22: A. Pelc, Searching with known error probability, Theoretical Computer Science, v.63 n.2, p.185-202, Feb. 1989 [doi>10.1016/0304-3975(89)90077-7]
• 23: Andrzej Pelc, Searching games with errors---fifty years of coping with liars, Theoretical Computer Science, v.270 n.1-2, p.71-109, January [doi>10.1016/S0304-3975(01)00303-6]
• 24: P.J. Plauger , Meng Lee , David Musser , Alexander A. Stepanov , Alexander Stepanov, C++ Standard Template Library, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 25: Bala Ravikumar, A Fault-Tolerant Merge Sorting Algorithm, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.440-447, August 15-17, 2002
• 26: A. Renyi. A diary on information theory, J. Wiley and Sons, 1994. Original publication: Naplo az informacioelmeletrol, Gondolat, Budapest, 1976.
• 27: S. M. Ulam. Adventures of a mathematician. Scribners (New York), 1977.
• 28: A. J. van de Goor, Testing semiconductor memories: theory and practice, John Wiley & Sons, Inc., New York, NY, 1991
• 29: A. C. Yao and F. F. Yao. On fault-tolerant networks for sorting. SIAM Journal on Computing, 14, 120--128, 1985.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Reliability, Theory

Keywords:
combinatorial algorithms, memory faults, memory models, searching, sorting