Set reconciliation based on counting Bloom filters - Xiao-mei TIAN; Da-fang ZHANG; Kun XIE; Can HU; Xiao-bo YANG; Chang-qiong SHI (Tongxin xuebao)
A new set reconciliation algorithm was presented,which called counting-Bloom-filter based set reconciliation(CBFSR).This method represented sets SA and SB as counting Bloom filters,subtracts SA's counting Bloom filter from SB's counting Bloom filter,the differences denoted CBF(SB)−CBF(SA),then determined SB−SA elements in SB with CBF(SB)−CBF(SA),and finally performed union operation on SB−SA and SA.Simulation resdts show counting-Bloom-filter based set reconciliation combines the advantages of exact set reconciliation and approximate set reconciliation,besides gaining all SB−SA elements with single-round messgage exchanges,it can apply to update-intensive distributed systems because counting Bloom filters support element deletion operation.