Skip to content

yangl1996/riblt

Repository files navigation

Implementation of Rateless Invertible Bloom Lookup Tables (Rateless IBLTs), as
proposed in paper Practical Rateless Set Reconciliation by Lei Yang, Yossi
Gilad, and Mohammad Alizadeh. Preprint available at
https://arxiv.org/abs/2402.02668.

Rateless IBLTs define for any set an infinite sequence of "coded symbols", each
being the same size as a set element. For any two sets, their coded symbol
sequences are sufficient for computing their symmetric difference, therefor
enabling synchronization. The number of coded symbols needed is linear to the
size of the symmetric difference, with the coefficient converging to 1.35 as
the difference goes to infinitely large.

A good starting point is example_test.go, a self-contained example of using
this package to synchronize two sets of integers.

Rust implementation available at:
https://github.com/Intersubjective/riblt-rust

About

Go implementation of Rateless IBLT.

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages