Set Reconciliation via Counting Bloom Filters

摘要

In this paper, we study the set reconciliation problem, in which each member of a node pair has a set of objects and seeks to deliver its unique objects to the other member. How could each node compute the set difference, however, is challenging in the set reconciliation problem. To address such an issue, we propose a lightweight but efficient method that only requires the pair of nodes to represent objects using a counting Bloom filter (CBF) of size $(O(d))$ and exchange with each other, where $(d)$ denotes the total size of the set differences. A receiving node then subtracts the received CBF from its local one via minus operation proposed in this paper. The resultant CBF can approximately represent the union of the set differences and thus the set difference to each node can be identified after querying the resultant CBF. In this paper, we propose a novel estimator through which each node can accurately estimate not only the value of $(d)$ but also the size of the set difference to each node. Such an estimation result can be used to optimize the parameter setting of the CBF to achieve less false positives and false negatives. Comprehensive analysis and evaluation demonstrates that our method is more efficient than prior BF-based methods in terms of achieving the same accuracy with less communication cost. Moreover, our reconciliating method needs no prior context logs and it is very useful in networking and distributed applications.