6
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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). Also, here is some subsequent work on this problem by the same authors: "Practical Set Reconciliation".

$\endgroup$
2
  • 3
    $\begingroup$ One of my recent papers is also on the same problem: 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. $\endgroup$ – David Eppstein Apr 11 '12 at 0:12
  • $\begingroup$ These references are exactly what I was looking for. Thank you! $\endgroup$ – a3nm Apr 12 '12 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.