JavaScript is disabled for your browser. Some features of this site may not work without it.
Set Reconciliation with Nearly Optimal Communication Complexity

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