EFFICIENT DETECTION OF DISCREPANCIES IN MULTIPLE FILE COPIES

For data consistency in distributed information systems, it is often n ecessary to compare remotely located copies of a file. We develop seve ral protocols for the efficient detection of differing pages in a repl icated file in different communication and failure models. The first s et of protocols assumes a restricted but practical communication model . In this case, the minimum amount of communication necessary to ident ify any given number of differing pages is determined and a technique to attain this minimum is presented. For the more general communicatio n model and for more refined failure models, we show that more efficie nt protocols can be derived. Our approach is based on the theory of Ga lois fields.