How Efficient Can Memory Checking Be?

We consider the problem of memory checking, where a user wants to maintain a large database on a remote server but has only limited local storage. The user wants to use the small (but trusted and secret) local storage to detect faults in the large (but public and untrusted) remote storage. A memory checker receives from the user store and retrieve operations to the large database. The checker makes its own requests to the (untrusted) remote storage and receives answers to these requests. It then uses these responses, together with its small private and reliable local memory, to ascertain that all requests were answered correctly, or to report faults in the remote storage (the public memory).

A fruitful line of research investigates the complexity of memory checking in terms of the number of queries the checker issues per user request (query complexity) and the size of the reliable local memory (space complexity). Blum et al., who first formalized the question, distinguished between online checkers (that report faults as soon as they occur) and offline checkers (that report faults only at the end of a long sequence of operations). In this work we revisit the question of memory checking, asking

how efficient can memory checking be?

For online checkers, Blum et al. provided a checker with logarithmic query complexity in

n

, the database size. Our main result is a lower bound: we show that for checkers that access the remote storage in a deterministic and non-adaptive manner (as do all known memory checkers), their query complexity must be at least

Ω

(log

n

/loglog

n

). To cope with this negative result, we show how to trade off the read and write complexity of online memory checkers: for any desired logarithm base

d

, we construct an online checker where either reading

or

writing is inexpensive and has query complexity

O

(log

d

n

). The price for this is that the other operation (write or read respectively) has query complexity

O

(

d

·log

d

n

). Finally, if even this performance is unacceptable,

offline

memory checking may be an inexpensive alternative. We provide a scheme with

O

(1) amortized query complexity, improving Blum et al.’s construction, which only had such performance for long sequences of at least

n

operations.