An application of group testing to the file comparison problem

The file comparison problem involves the detection of differences between two copies of the same file located at different sites in a distributed computing system. The file is assumed to be partitioned into n pages, and a signature (checksum) is available for each page. Some ideas from nonadaptive group testing are used to obtain a solution to this problem for the case of arbitrary d, where d is a fixed bound on the maximum number of differing pages. A deterministic construction is presented which, for the special case d=2, improves upon previous results. For values of n<2²⁰ and d⩽10, the construction results in a substantially smaller number of composite signatures than the best-known asymptotic upper bound