Fault Tolerant Data Structures

We consider the tolerance of data structures to memory faults. We 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. In this paper we present a formal framework for studying the fault tolerance properties of pointer-based data structures, and we provide fault tolerant versions of the stack, the linked list, and the dictionary tree. 1 Introduction Motivation. We consider the tolerance of pointer-based data structures to memory failures (e.g. disk sector failures, main memory erasures, accidental overwrites, etc.). We observe that many commonly-used data structures are highly nonresilient to faults. Consider, for example, the linked list. Losing a single pointer makes the entire tail of the list unreachable. Thus, one fault may result in losing an unbounded amount of data (on average n=2 nodes are lost, for a list of size n). Trees, st..