Efficient Reconciliation of Unordered Databases

Abstract

We consider the problem of reconciling two unordered databases whose contents are related. Specifically, we wish to determine the mutual difference of these databases with a minimum communication complexity. This type of problem arises naturally in the context of gossip protocols. We analyze two instances of the reconciliation problem, a client-server model and a more general peer-to-peer model, and provide interactive solutions for both. For the former instance, we also provide a simple one-message reconciliation algorithm, based on elementary symmetric polynomials, which has an almost optimal communication complexity.