Practical Set Reconciliation Implementation

Version: Beta 0.998

Initial implementation by Sachin Agarwal, Boston University (
Modifications by Ari Trachtenberg, Boston Unviersity (

Theoretical references:

(available at 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


  1. Download the source code.
  2. Type the following at the unix prompt: ./configure make
  3. 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 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.