Checking linked data structures

Nancy M. Amato, Michael C. Loui

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the program checking paradigm, the original program is run on the desired input, and its output is checked by another program called a checker. Recently, the notion of program checking has been extended from its original formulation of checking functions to checking a sequence of operations which query and alter the state of an object external to the program, e.g., checking the interactions between a client and the manager (server) of a data structure. In this expanded paradigm, the checker acts as an intermediary between the client, which generates the requests, and the server, which processes them. The checker is allowed a small amount of reliable memory and may provide a probabilistic guarantee of correctness for the client. We present off-line and on-line checkers for data structures such as linked lists, trees, and graphs. Previously, the only data structures for which such checkers existed were random access memories, stacks, and queues.

Original languageEnglish (US)
Title of host publicationDigest of Papers - International Symposium on Fault-Tolerant Computing
PublisherPubl by IEEE
Pages164-173
Number of pages10
ISBN (Print)0818655224
StatePublished - 1994
EventProceedings of the 24th International Symposium on Fault-Tolerant Computing - Austin, TX, USA
Duration: Jun 15 1994Jun 17 1994

Publication series

NameDigest of Papers - International Symposium on Fault-Tolerant Computing
ISSN (Print)0731-3071

Other

OtherProceedings of the 24th International Symposium on Fault-Tolerant Computing
CityAustin, TX, USA
Period6/15/946/17/94

ASJC Scopus subject areas

  • Hardware and Architecture
  • General Engineering

Fingerprint

Dive into the research topics of 'Checking linked data structures'. Together they form a unique fingerprint.

Cite this