Range-Based Set Reconciliation (negentropy)

[hoytech]

Hi! Have you seen the set reconcilliation algorithm described here? https://arxiv.org/abs/2212.13567

I wrote a C++ library that defines and implements this as a concrete protocol: https://github.com/hoytech/negentropy

Before building negentropy, I looked into the algorithms that gensync implements, and my conclusion was that range-based reconcilliation is superior under most conditions:

• Handles very large cardinalities (we are routinely using it for syncing data-sets of size 10 million, and greater)
• No tuning required: works predictably well with large or small number of differences
• Bandwidth overhead is logarithmic in DB size and linear in number of symmetric differences
• Negligible CPU usage compared with CPISync/minisketch
• No false positives or failed decodes like with bloom-filter based algos

But I would love to have some objective benchmarks to verify this (or be proven mistaken!).

Thanks for any help!

[trachten]

Hi … sorry for the slow response; I was away. Is the arxiv version the latest version of your work, or is the a later version published in a conference or journal venue? Please feel free to reach out directly to ***@***.*** ***@***.***>. best, -Ari

…

On Aug 16, 2023, at 1:05 AM, Doug Hoyte ***@***.***> wrote: Have you seen the set reconcilliation algorithm described here: https://arxiv.org/abs/2212.13567 I wrote a C++ library that defines and implements this as a concrete protocol: https://github.com/hoytech/negentropy Before building negentropy, I looked into the algorithms that gensync implements, and my conclusion was that range-based reconcilliation is superior under most conditions: Handles very large cardinalities (we are routinely using it for syncing data-sets of size 10 million, and greater) No tuning required: works predictably well with large or small number of differences Bandwidth overhead is logarithmic in DB size and linear in number of symmetric differences Negligible CPU usage compared with CPISync/minisketch <https://github.com/sipa/minisketch> No false positives or failed decodes like with bloom-filter based algos But I would love to have some objective benchmarks to verify this (or be proven mistaken!). Thanks for any help! — Reply to this email directly, view it on GitHub <#9>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACM5LU6ENP3BBUHENUW2UOLXVRIH5ANCNFSM6AAAAAA3R6ZZMY>. You are receiving this because you are subscribed to this thread.

[hoytech]

No worries. The paper that I posted is not my work, it is by @AljoschaMeyer

The negentropy implementation is my C++ implementation of his algorithm. I don't know if it's been published or not.

I can't see those email addresses, they just got turned into * characters, probably by github?

[AljoschaMeyer]

Hi @trachten,

the paper was accepted at SRDS23, so it should be published shortly. Until then, here is the camera-ready submission:
main.pdf

[AljoschaMeyer]

I would be happy to answer any questions or be kept in the loop regarding range-based reconciliation in gensync. I had planned to do some benchmarking for various choices of protocol parameters (recursion anchors, branching degree, fingerprint monoid), auxiliary data structures, and comparisons with MSTs, but there's no code yet (and I have prioritized other projects so far). A Master's student is currently doing some work in that area under my (informal) supervision though.

I have not written a single line of C++ in my life however, though branching over from rust and C should not be too much of a problem.

[trachten]

Thanks for the update! My email is also at the bottom of the README.md file on github (https://github.com/nislab/gensync). It would be great to integrate your implementation into gensync so that we could do an apples-to-apples comparison ... if you don't have the time for it, I can see if I can find an MS student who would like to do it as part of an MS project. best, -Ari

On Aug 28, 2023, at 11:31 AM, Doug Hoyte ***@***.***> wrote: No worries. The paper that I posted is not my work, it is by @AljoschaMeyer <https://github.com/AljoschaMeyer> The negentropy implementation is my C++ implementation of his algorithm. I don't know if it's been published or not. I can't see those email addresses, they just got turned into * characters, probably by github? — Reply to this email directly, view it on GitHub <#9 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACM5LU3CZ6MPQKPFE2ZGAM3XXS2TXANCNFSM6AAAAAA3R6ZZMY>. You are receiving this because you commented.

— Prof. Ari Trachtenberg Electrical and Computer Engineering Boston University ***@***.***

[trachten]

Thanks @AljoschaMeyer <https://github.com/AljoschaMeyer> for the paper draft and the comments! I think that GenSync could be an excellent framework for a practical comparison ...

On Aug 29, 2023, at 4:57 AM, Aljoscha Meyer ***@***.***> wrote: I would be happy to answer any questions or be kept in the loop regarding range-based reconciliation in gensync. I had planned to do some benchmarking for various choices of protocol parameters (recursion anchors, branching degree, fingerprint monoid), auxiliary data structures, and comparisons with MSTs <https://inria.hal.science/hal-02303490/file/paper%20%281%29.pdf>, but there's no code yet (and I have prioritized other projects so far). A Master's student is currently doing some work in that area under my (informal) supervision though. I have not written a single line of C++ in my life however, though branching over from rust and C should not be too much of a problem. — Reply to this email directly, view it on GitHub <#9 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACM5LU4NGL544XROKABW7DTXXWVIDANCNFSM6AAAAAA3R6ZZMY>. You are receiving this because you were mentioned.

— Prof. Ari Trachtenberg Electrical and Computer Engineering Boston University ***@***.***

[hoytech]

Great! I will take a stab at integrating it, when I find some time. Or if you have any interested student in the mean-time I'm happy to help them with negentropy API.