Fault Tolerant Data Structures

The authors consider the tolerance of data structures to memory faults. They observe that many pointer-based data structures (e. g. linked lists, trees, etc.) are highly nonresilient to faults. A single fault in a linked list or tree may result in the loss of the entire set of data. They present a formal framework for studying the fault tolerance properties of pointer-based data structures, and provide fault tolerant versions of the stack, the linked list, and the dictionary tree.

Authors

• Yonatan Aumann
• Michael A. Bender

Keywords

• Fault tolerance
• Data structures
• Tree data structures
• Resilience
• Dictionaries
• Tail
• Application software
• Mathematics
• Computer science
• Laboratories
• Data Structure
• Fault-tolerant
• Time Complexity
• Nodes In The Graph
• File System
• Binary Tree
• Forward Error Correction
• Blocking Layer
• Graph Topology
• Reconstruction Time
• Consecutive Layers