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/5788
Title: Set Reconciliation with Nearly Optimal Communication Complexity
Authors: Minsky, Yaron
Trachtenberg, Ari
Zippel, Richard
Keywords: computer science
technical report
Issue Date: 28-Apr-2000
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR2000-1796
Abstract: We consider a fundamental problem that arises in the context of gossip protocols. Specifically, we consider the problem of efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity. We provide two surprisingly simple and efficient protocols that exhibit tractable computational complexity and nearly optimal communication complexity. These protocols can be adapted to work over a broadcast channel, allowing many clients to reconcile with one host based on a broadcasted signal.\note{We keep on bouncing back and forth on whether the ``a''s are necessary. I like it better without, but it's not a big deal.} Thus, an arbitrary number of clients each of whose data differs from that of the host by no more than $N$ bits can be reconciled by a single broadcast of $O(N)$ bits, independent of the the number of clients and independent of the size of the data sets.
URI: http://hdl.handle.net/1813/5788
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
2000-1796.pdf246.54 kBAdobe PDFView/Open
2000-1796.ps252.28 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us