Low complexity set reconciliation using Bloom filters
Magnus Skjegstad, Torleiv Maseng · 2011
In many distributed protocols efficient synchronization of data elements is a determining factor for both bandwidth usage and computational requirements. Earlier works have shown that by using error correcting codes and probabilistic membership tests, sets can be reconciled with near optimal bandwidth complexity. In this paper, we propose an alternative method with low computational requirements. Although the bandwidth requirements are not optimal, we show that our mechanism performs well when the number of differences between the sets are unknown. As the mechanism requires very little state information to be transferred, any node may reply to synchronization requests after receiving a single message. This enables fast synchronization in dynamic networks, as well as simultaneous synchronization of multiple nodes within radio broadcast range. We expect these properties to be desirable for many applications in mobile environments.