# Practical Set Reconciliation Implementation

Version: Beta 0.998

06/22/2004

Initial implementation by Sachin Agarwal, Boston University (ska@bu.edu)

Modifications by Ari Trachtenberg, Boston Unviersity (trachten@bu.edu)
## Theoretical references:

(available at http://people.bu.edu/trachten)
Original set reconciliation algorithm:
Y. Minsky, A. Trachtenberg, and R. Zippel,
Set Reconciliation with Nearly Optimal Communication Complexity,
IEEE Transactions on Information Theory 49:9, pp. 2213-2218
-and-
IEEE International Syposium on Information Theory 2001.
Scalable set reconciliation algorithm:
Y. Minsky and A. Trachtenberg, Practical Set Reconciliation,
40th Annual Allerton Conference on Communication, Control, and Computing,
October 2002.
Implementation on Personal Digital Assistant devices:
D. Starobinski, A. Trachtenberg, and S. Agarwal,
Efficient PDA synchronization,
IEEE Transactions on Mobile Computing 2:1
A. Trachtenberg, D. Starobinski, and S. Agarwal,
Fast PDA Synchronization Using Characteristic Polynomial Interpolation,
IEEE INFOCOM 2002
## Installation:

- Download the source code.
- Type the following at the unix prompt:
./configure
make
- You can test the system with:
make test

The configure script will try to install the GMP and NTL libraries
into subdirectories. Alternatively, the following websites provide more
details on these standard math libraries:
## Usage:

Usage instructions are available in the source file *usage.txt*.

Note: This release has been tested partially , but not yet methodically.
Contact the authors with any bugs and / or comments. Please acknowledge
the authors and/or the theoretical references if you make use of this code.