Set Reconciliation with Cuckoo Filters
Lailong Luo, Deke Guo, Ori Rottenstreich, Richard T. B. Ma, Xueshan Luo · 2019
Set reconciliation is a common and fundamental task in distributed systems. In many cases, given set A on $Host_A$ and set B on $Host_B$, applications need to identify those elements that appear in set A but not in set B, and vice versa. However, existing methods incur unsatisfactory space utilization and non-trivial false positives and false negatives. In this paper, we present a novel reconciliation method based on Cuckoo filter (CF). After exchanging the CFs each of which represents a set of elements, we query the local elements against the received CF to determine the elements that only belong to the local host and should be transmitted to the other host. The evaluation results indicate that the CF-based reconciliation method outperforms existing methods significantly.