This talk is based on the FOCS 96 paper from Y. Aumann and M. Bender. The authors showed fault tolerant versions of three common data structures. In this talk, we will cover fault tolerant versions of stack and the linked list in detail.
Paper Abstract:
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 lost 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.