<p>This appears to be known as the "set reconciliation" problem. The key paper appears to be <a href="http://stafisfics.tribler.org/trac/raw-attachment/wiki/IPv8/Set%20reconciliation%20with%20nearly%20optimal%20communication%20complexity.pdf">Minsky &amp; Trachtenberg, "Set Reconciliation With Nearly Optimal Communication Complexity", IEEE Transactions on Information Theory (2003)</a>. Also, here is some subsequent work on this problem by the same authors: <a href="http://cis.poly.edu/westlab/papers/ref/practical.pdf">"Practical Set Reconciliation"</a>.</p>

CC BY-SA 3.0
2012-04-11T00:12:55.860Z
One of my recent papers is also on the same problem: http://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf — I think in terms of total information transmitted it is a little worse than M&T (so I'm not leaving it as a separate answer) but it uses fewer rounds of communication and is easier to decode.
David Eppstein
CC BY-SA 3.0
2012-04-12T07:43:25.403Z
These references are exactly what I was looking for. Thank you!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-04-10T23:49:11.833Z
2012-04-10T23:49:11.833Z
mhum
<p>We consider two computers who possess two sets of fixed-size values (ie. $k$-bit numbers for some constant $k$), and we assume that the two sets have a large overlap (ie. a large proportion of the values are present on both hosts). We want to find an protocol to synchronize the two sets (ie. give to each host the knowledge of the values of the other hosts) in a way which minimizes the quantity of information transferred between the two hosts.</p>

<p>In particular, if we denote by $N_1$, $N_2$ the size of the sets and $K_1$ (resp. $K_2$) the number of values present only on computer 1 (resp. only on computer 2), the trivial algorithm where both computers exchange their sets is $O(N_1+N_2)$, and the trivial lower bound on the quantity of information to exchange is $O(K_1+K_2)$. Is it possible to reach this bound?</p>

<ds.algorithms><dc.distributed-comp><it.information-theory>
Minimal bandwidth required to synchronize two sets of values
Antoine Amarilli 'a3nm'
# Minimal bandwidth required to synchronize two sets of values

(Asked by: username_0 on 2012-04-10)

We consider two computers who possess two sets of fixed-size values (ie. $k$-bit numbers for some constant $k$), and we assume that the two sets have a large overlap (ie. a large proportion of the values are present on both hosts). We want to find an protocol to synchronize the two sets (ie. give to each host the knowledge of the values of the other hosts) in a way which minimizes the quantity of information transferred between the two hosts.

In particular, if we denote by $N\_1$, $N\_2$ the size of the sets and $K\_1$ (resp. $K\_2$) the number of values present only on computer 1 (resp. only on computer 2), the trivial algorithm where both computers exchange their sets is $O(N\_1+N\_2)$, and the trivial lower bound on the quantity of information to exchange is $O(K\_1+K\_2)$. Is it possible to reach this bound?

**Tags:** ds.algorithms, dc.distributed-comp, it.information-theory


---

## 1 answers

### Answer by username_1 on 2012-04-10. Score: 6 | Accepted answer

This appears to be known as the "set reconciliation" problem. The key paper appears to be [Minsky & Trachtenberg, "Set Reconciliation With Nearly Optimal Communication Complexity", IEEE Transactions on Information Theory (2003)](http://stafisfics.tribler.org/trac/raw-attachment/wiki/IPv8/Set%20reconciliation%20with%20nearly%20optimal%20communication%20complexity.pdf). Also, here is some subsequent work on this problem by the same authors: ["Practical Set Reconciliation"](http://cis.poly.edu/westlab/papers/ref/practical.pdf).

> **Comments:**
> **username_2**: One of my recent papers is also on the same problem: http://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf — I think in terms of total information transmitted it is a little worse than M&T (so I'm not leaving it as a separate answer) but it uses fewer rounds of communication and is easier to decode.  
> **username_0**: These references are exactly what I was looking for. Thank you!  

---

