Title:  Fast Approximate Reconciliation of Set Differences

Authors:  John W. Byers, Jeffrey Considine and Michael Mitzenmacher

Date: 7/11/02

Abstract:

We present new, simple, efficient data structures for approximate
reconciliation of set differences, a useful standalone primitive for
peer-to-peer networks and a natural subroutine in methods for exact
reconciliation. In the approximate reconciliation problem, peers A and
B respectively have subsets of elements S(A) and S(B) of a large
universe U.  Peer A wishes to send a short message M to peer B with
the goal that B should use M to determine as many elements in the set
S(B) - S(A) as possible.  To avoid the expense of round trip
communication times, we focus on the situation where a single message
M is sent.

We motivate the performance tradeoffs between message size, accuracy
and computation time for this problem with a straightforward approach
using Bloom filters.  We then introduce approximation reconciliation
trees, a more computationally efficient solution that combines
techniques from Patricia tries, Merkle trees, and Bloom filters.  We
present an analysis of approximation reconciliation trees and provide
experimental results comparing the various methods proposed for
approximate reconciliation.