Accession Number : ADA186898

Title :   Local Concurrent Error Detection and Correction in Data Structures using Virtual Backpointers.

Descriptive Note : Technical rept.,

Corporate Author : ILLINOIS UNIV AT URBANA COLL OF ENGINEERING

Personal Author(s) : LI, C C

PDF Url : ADA186898

Report Date : Oct 1987

Pagination or Media Count : 41

Abstract : A new technique, based on virtual backpointers, for local concurrent error detection and correction in linked data structures is presented in this paper. Two new data structures, the Virtual Double linked List, and the B tree with Virtual Backpointers, are described. For these structures, double errors can be detected in 0(1) time. The application of a concurrent auditor process to data structure error detection and correction is analyzed, ans an implementation is described, to determine the effect on the mean time to failure of a multi-user shared-database system. The implementation utilizes a sequential shared memory multiprocessor system operating on a shared databased of Virtual Double Linked Lists. Keywords: Concurrent error detection, Data structures, Concurrent structure checking.

Descriptors :   *DATA BASES, *DATA MANAGEMENT, *ERRORS, *MULTIPROCESSORS, DETECTION, FAILURE, LINKAGES, MEAN, MEMORY DEVICES, TIME, TIME SHARING

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE