TY - GEN
T1 - Checking linked data structures
AU - Amato, Nancy M.
AU - Loui, Michael C.
PY - 1994
Y1 - 1994
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0027982730&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027982730&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0027982730
SN - 0818655224
T3 - Digest of Papers - International Symposium on Fault-Tolerant Computing
SP - 164
EP - 173
BT - Digest of Papers - International Symposium on Fault-Tolerant Computing
PB - Publ by IEEE
T2 - Proceedings of the 24th International Symposium on Fault-Tolerant Computing
Y2 - 15 June 1994 through 17 June 1994
ER -