On: The Periodic Table of Data Structures [pdf]

[the8472]

One way to do this is to send a bloom filter as index and then return the elements that are not part of the bloom filter.

[jpitz → the8472]

But what about the false positives?

[jwhitlark → jpitz]

Well, I would assume the receiving node would verify that each entry was actually needed.

[jpitz → jwhitlark]

Aren't the false positives in this situation representative of set elements that node b thinks that node a has but really does not?

[the8472 → jpitz]

Right, the solution I remembered was a bit more complex, it required counting bloom filters and a subtraction operation to get a filter for the set difference. But the paper mentioned in a sibling comment claims to have even less overhead.