Anyone interested in IBLT with low failure probablity should also be aware of pinsketch and, particularly, our implementation of it: minisketch ( https://github

Anyone interested in IBLT with low failure probablity should also be aware of pinsketch and, particularly, our implementation of it: minisketch ( https://github.com/sipa/minisketch/ https://github.com/sipa/minisketch/ ). Our implementation communicates a difference of <=N b-bit entries with exactly N*b bits with 100% success. The cost for this communications efficiency and reliability is that the decoder takes CPU time quadratic in N, instead of IBLT's linear decoder. However, when N is usually small, if the implementation is fast this can be fine -- especially since you wouldn't normally want to use set recon unless you were communications limited. For the sketch sizes (both low N and low bits per entry) we were interested in for relaying transactions in the Bitcoin network pinsketch/minisketch is more than a dozen times more communications efficient than low failure rate iblt. The concrete efficiency of this paper isn't yet clear to me-- though at a glance I think it also will not be great for small sizes only asymptotically (which is, of course, also where the computational costs are also an issue). Pinsketches and iblt can also be combined-- one can use pinsketches as the cells of an iblt and one can also use a small pinsketch to improve the failure rate of an iblt (since when a correctly sized IBLT fails, it's usually just due to a single undecodable cycle) which can be corrected using pinsketch by only a tiny amount of data.