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 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.
Date Issued
2000-09-27Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR2000-1813
Type
technical report