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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1987
Accession Number
ADA186898

Entities

People

  • C. C. Li

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Access Time
  • Boundaries
  • Classification
  • Clocks
  • Computations
  • Contracts
  • Detection
  • Illinois
  • Lists (Data Structures)
  • Military Research
  • Probability
  • Random Variables
  • Security
  • Semantic Models
  • Time Intervals
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Engineering

Readers

  • Computer Programming and Software Development.
  • Neural Network Machine Learning.
  • Parallel and Distributed Computing.