Set Reconciliation with Nearly Optimal Communication Complexity
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
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