Accession Number : ADA255499
Title : Fault-Tolerant Wait-Free Shared Objects
Descriptive Note : Technical rept.
Corporate Author : CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE
Personal Author(s) : Jayanti, Prasad ; Chandra, Tushar D ; Toueg, Sam
Report Date : Aug 1992
Pagination or Media Count : 58
Abstract : A concurrent system consists of processes and shared objects. Previous research focused on the problem of tolerating process failures. We study the complementary problem of tolerating object failures. We divide object failures into two broad classes: responsive and non-responsive. With responsive failures, a faulty object responds to every invocation, but responses may be incorrect. With non-responsive failures, a faulty object may also hang without responding. For each class, we consider crash, omission, and arbitrary types of failures. For each type of failure, we are seeking a universal implementation for fault-tolerant wait-free shared objects. We present (deterministic) implementations for all types of responsive failures, including arbitrary failures. In contrast, we show that even the most benign type of non-responsive failures requires the use of randomization. Of special interest is the problem of implementing fault-tolerant objects using only objects of the same type. We present such fault-tolerant self-implementations for many common object types.
Descriptors : *FAULT TOLERANT COMPUTING , *FAILURE(ELECTRONICS) , CONTRAST , CRASHES , FAULTS , FAILURE
Subject Categories : Computer Hardware
Distribution Statement : APPROVED FOR PUBLIC RELEASE