Practical Rateless IBLT: Part 1
guiltygyoza.xyz Practical rateless IBLT: Part 1 |
AI summary of the linked articleThis two-part post presents a digest of the PRIBLT paper, and Part 1 sets up set reconciliation and surveys prior approaches. The central idea is that PRIBLT makes IBLT rateless and practical, so the sender streams codes until the receiver can decode, with no need to guess the size of the set difference. Alice and Bob, the post's example pair, exchange codes by phone until Bob signals that decoding has succeeded. The article says that on average between 1.35d and 1.72d codes are needed, where d is the size of the set difference, even with millions of items in each bag. |
Recommended by 1 curator |
2 comments Very cool! I love that this seems to be non-interactive. My biggest issue with Patricia Merkle Trees is that their reconciliation is interactive any hence requires a lot of networking logic, which is very easy to run into issues and hard to code right! I feel uneasy though having to pick a size for the set, so I want to explore more what guiltygyoza suggests towards the end of the post |
