JavaScript is disabled for your browser. Some features of this site may not work without it.
Efficient Reconciliation of Unordered Databases

Author
Minsky, Yaron; Trachtenberg, Ari
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.
Date Issued
1999-11Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR99-1778
Type
technical report