Comment by DoctorOetker | Hacker News Reader

Comment by DoctorOetker | Hacker News Reader

this is probably off topic, but I've waited before asking until I found the closest topic from my perspective:

A while back (order months or years but certainly within last 2 years) someone mentioned a paper, I believe it was here on HN either as the topic or in a comment, but perhaps it may have been on IRC.

I am no longer able to find back this paper, and have only a vague recollection of it (I had read the abstract and the introduction and then postponed reading until I forgot about it).

It dealt with the problem of say 2 peers each having their own list or set, and part of their list is in common, but both may also have entries the other doesn't have. The problem was finding the most efficient way such that both end up with the union of both lists or sets. A brute force way would be to each send a copy of their list to the other, a slightly less brute way would be to have only one send a full copy, and have the other return his difference. But the paper detailed a more efficient method, which obviously I can't remember...

Does this description ring a bell? Does anyone know the paper I am trying to locate?

https://ieeexplore.ieee.org/document/1226606?reload=true&par...

I actually have a similar question to yours--I lost track of a set of notes that was linked to in a HN comment, and would like to find them again!

The notes were a (draft?) PDF for a textbook on algorithms--much like Mathematics for Computer Science by Lehman & Leighton [1]--but instead, the topic was narrowly restricted to algorithms with a cryptographic or otherwise number-theoretic basis. In particle, hashes, content-addressable storage, and Merkle-trees were covered.

[1] https://courses.csail.mit.edu/6.042/spring18/mcs.pdf

Not this one by any chance?

Boaz Barak, "An Intensive Introduction to Cryptography"

https://news.ycombinator.com/item?id=17896692

Very interesting. I can't actually decide if this was what I had in mind, but it actually looks better. Thanks!

Perhaps "A Computational Introduction to Number Theory and Algebra" by Victor Shoup? This was recommended by Dan Boneh in his crypto course.

Another interesting book, so thanks, but perhaps less likely even, since I recall it had some material on things having to do with hash-based file systems (I recall seeing material on Merkle trees).

This isn't new, and doesn't answer that part of your question, but a Merkle Tree is a solution to that problem that can avoid sending the entire set.

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.

But what about the false positives?

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

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

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.

Reply on news.ycombinator.com