|
Abstract : |
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. More interestingly, we show by means of an explicit construction that the problem of reconciliation is, under certain general conditions, equivalent to the problem of finding good error-correcting codes. We show analogous results for the problem of multi-set verification, in which we wish to determine whether two multi-sets 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., |
