Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7432
Title: Efficient Reconciliation of Unordered Databases
Authors: Minsky, Yaron
Trachtenberg, Ari
Keywords: computer science
technical report
Issue Date: Nov-1999
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR99-1778
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.
URI: http://hdl.handle.net/1813/7432
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
99-1778.pdf277.84 kBAdobe PDFView/Open
99-1778.ps420.22 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us