Efficient false positive free set synchronization using an extended bloom filter approach

Synchronization between two sets is an important requirement for many distributed applications. A basic prerequisite is to find out which elements of set A are not in set B and vice versa. A very space efficient data structure for such membership queries that has been used a lot in networking applications is the Bloom filter. Unfortunately, the Bloom filter owes its high efficiency to the fact that there is a chance of false positives when querying the filter. This precludes the adoption of Bloom filters in applications that cannot tolerate such errors. In this paper we present an approach that augments Bloom filters with a trie-based mechanism that deterministically and efficiently finds the false positives after using the Bloom filter to synchronize two sets. We show that the added communication overhead for our approach is negligible compared to the overhead of a plain Bloom filter.