This clearly written and well-organized paper makes two significant contributions to the field of robust storage structures: an enhanced theory of local error detection and correction, and the concept of a virtual backpointer. Although a full understanding of the paper probably requires familiarity with previous work on robust storage structures, the main ideas can be understood without any specialized background.

Local error detection and correction must be performed using only data located near the error. Previous work on local error detection and correction required only that there be a constant bound on the amount of data used. The authors introduce the concept of a checking window to specify how much of the structure may be used by a step of the detection or correction procedure.

A virtual backpointer is a backward pointer value that is stored using an invertible function of the value and other, explicitly stored, pointer values. For example, the back pointer field in a double-linked list can be replaced by a virtual backpointer: the exclusive-or of the forward and back pointer values. The virtual double-linked list (VDLL) and the B-tree with virtual backpointers (VBT) described in the paper demonstrate that this technique can increase robustness without increasing storage space. The VDLL structure is likely to have considerable practical value. The VBT has the unappealing property of containing pointers that address fields within a node, and it may be of less practical value.

Empirical results demonstrate that the detection technique is highly effective when applied to these two structures (no undetected errors occurred). Error correction was also quite successful, although explicit comparison with experimental results in other robust linked lists and B-trees would provide additional perspective on the results presented.