README.md

An implementation of multi-party set reconciliation using Inverible Bloom Lookup Tables. Handles an arbitrary number of parties (with optimizations for the two-party case), and multiple key formats (either primitives or std::strings of arbitrary length), both through template parameters.

To test the multi-party IBLTS:

$ make
$ ./bin/multi_testing

Upper bounding the set difference is an important problem in set reconciliation. We implement the Strata Estimator designed here.

IBLTs and Strata Estimators are used as sub-component of our file synchronization protocol, which shares many similarities to the one explained in this paper.

To test the file synchronization protocol:

$ ./bin/file_sync_testing [file1] [file2]

Requirements:

1. Google's Protocol Buffer, which we use for (de)serialization of messages

2. zlib, which we use for compression

3. openssl which we use for SHA-1 hash.

$ sudo apt-get install libssl-dev

4. boost

$ sudo apt-get instal libboost-all-dev

This repo also contains implementations of basic tabluation hashing, "field" arithmetic, and document fingerprinting using winnowing.

Each can be tested separately (refer to Makefile for appropriate commands).