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/5803
Title: Set Reconciliation with Nearly Optimal Communication Complexity
Authors: Minsky, Yaron
Trachtenberg, Ari
Zippel, Richard
Keywords: computer science
technical report
Issue Date: 27-Sep-2000
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR2000-1813
Abstract: We consider the problem of efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity. This type of problem arises naturally from gossip protocols used for the distribution of information. We describe an aproach to set reconciliation based on the encoding of sets as polynomials. The resulting protocols exhibit tractable computational complexity and nearly optimal communication complexity. Also, these protocols can be adapted to work over a broadcast channel, allowing many clients to reconcile with one host based on a single broadcast, even if each client is missing a different subset.
URI: http://hdl.handle.net/1813/5803
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
2000-1813.pdf301.71 kBAdobe PDFView/Open
2000-1813.ps338.52 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us