Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Data structures resilient to memory faults: an experimental study of dictionaries
Ferraro-Petrillo U., Grandoni F., Italiano G. Journal of Experimental Algorithmics18 1.1-1.14,2013.Type:Article
Date Reviewed: Dec 27 2013

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.

Reviewer:  Paparao Kavalipati Review #: CR141838 (1403-0218)
Bookmark and Share
  Featured Reviewer  
 
Data Structures (E.1 )
 
 
Algorithm Design And Analysis (G.4 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Data Structures": Date
Handbook of algorithms and data structures
Gonnet G. (ed), Baeza-Yates R., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991. Type: Book (9780201416077)
Feb 1 1992
Data structures and algorithm analysis
Weiss M., Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1992. Type: Book (9780805390544)
Aug 1 1992
Data structures and program design in C
Kruse R., Leung B., Tondo C., Prentice-Hall, Inc., Upper Saddle River, NJ, 1992. Type: Book (9780137256495)
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy