Detecting corrupted pages in M replicated large files

Abstract

A file in a distributed database system is replicated on M sites and may contain corrupted pages. Abdel-Ghaffar and El Abbadi gave a detection scheme assuming that the number of corrupted pages f < M/2. We replace this assumption by a much weaker one, that, for each page, the majority of copies are correct. Our schemes are based on the structure of the Reed-Solomon code, as proposed by Abdel-Ghaffar and El Abbadi for M = 2.