Checking the correctness of memories

Abstract

The notion of program checking is extended to include programs that alter their environment, in particular, programs that store and retrieve data from memory. The model considered allows the checker a small amount of reliable memory. The checker is presented with a sequence of requests (online) to a data structure which must reside in a large but unreliable memory. The data structure is viewed as being controlled by an adversary. The checker is to perform each operation in the input sequence using its reliable memory and the unreliable data structure so that any error in the operation of the structure will be detected by the checker with high probability. Checkers for various data structures are presented. Lower bounds of log n on the amount of reliable memory needed by these checkers, where n is the size of the structure, are proved.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>