Data verification and reconciliation with generalized error-control codes
Mark G. Karpovsky, Lev B. Levitin, Ari Trachtenberg · IEEE Transactions on Information Theory · 2003
We consider the problem of data reconciliation, which we model as two separate multisets of data that must be reconciled with minimum communication. Under this model, we show that the problem of reconciliation is equivalent to a variant of the graph coloring problem and provide consequent upper and lower bounds on the communication complexity of reconciliation. Further, we show by means of an explicit construction that the problem of reconciliation is, under certain general conditions, equivalent to the problem of finding error-correcting codes for a general class of errors. Under this equivalence, reconciling with little communication is linked to codes with large size, and vice versa. We show analogous results for the problem of multiset verification, in which we wish to determine whether two multisets are equal using minimum communication. As a result, a wide body of literature in coding theory may be applied to the problems of reconciliation and verification.