Fault tolerant data structures

Yonatan Aumann; Michael A. Bender

Fault tolerant data structures

Yonatan Aumann
, Michael A. Bender

Computer Science

Stony Brook University

Bar-Ilan University

Research output: Contribution to journal › Conference article › peer-review

53 Scopus citations

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 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.

Original language	English
Pages (from-to)	580-589
Number of pages	10
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
State	Published - 1996
Event	Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science - Burlington, VT, USA Duration: Oct 14 1996 → Oct 16 1996

Cite this

@article{c1f6789688b24acea63e7d1d8eaab0f7,

title = "Fault tolerant data structures",

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 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.",

author = "Yonatan Aumann and Bender, \{Michael A.\}",

year = "1996",

language = "English",

pages = "580--589",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

publisher = "IEEE Computer Society",

note = "Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science ; Conference date: 14-10-1996 Through 16-10-1996",

}

TY - JOUR

T1 - Fault tolerant data structures

AU - Aumann, Yonatan

AU - Bender, Michael A.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0030416136

M3 - Conference article

SN - 0272-5428

SP - 580

EP - 589

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science

Y2 - 14 October 1996 through 16 October 1996

ER -

Fault tolerant data structures

Abstract

Other files and links

Fingerprint

Cite this