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 is a layer between the user and the remote storage, that receives from the user a sequence of 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 that the remote storage (sometimes referred to as the public memory) was faulty.
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). We distinguish between online (that report faults as soon as they occur) and offline (that report faults only at the end of a long sequence of operations) checkers. In this work we revisit the question of memory checking, trying to reduce the overhead incurred by memory checkers and addressing the issue of how efficient can memory checking be?
For online checkers, Blum et al. (see here) 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 W(log n / loglog n). Still, we ask whether in some settings the logarithmic query complexity can be avoided. To answer this question, we show how to trade off the read and write complexity of online memory checking: for any desired logarithm base d, we show how to build 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, off-line memory checking may be an inexpensive alternative: for offline checkers we provide a scheme with O(1) amortized query complexity. This improves on the Blum et al. construction that only had such performance for long sequences of operations.
Postscript , gzipped Postscript , PDF .