Set Reconciliation with Nearly Optimal Communication Complexity

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.