Minimal bandwidth required to synchronize two sets of values 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?
This appears to be known as the "set reconciliation" problem. The key paper appears to be Minsky &amp; 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".