Local concurrent error detection and correction in data structures using virtual backpointers

A technique that uses the concepts of the checking window and the virtual backpointer is presented. The checking window was used to define the locality in which local concurrent error detection and correction are performed, and also to state specifically the size of that locality. The virtual backpointer was used to construct two new data structures: the virtual double-linked list, which requires the same storage as the standard double-linked list, and the B-tree with virtual-backpointers of order m, which requires m+4 extra fields per node. For these structures, double errors can be detected in constant time and single errors detected during forward moves can be corrected in constant time.<>