False Rate Analysis of Bloom Filter Replicas in Distributed Systems

Bloom filters have been widely used in distributed systems where they are replicated to process distributed queries. Bloom filter replicas become stale in a dynamic environment. A good understanding of the impact of staleness on false negatives and false positives can provide the system designers with important insights into the development and deployment of distributed Bloom filters in many distributed systems. To our best knowledge, this paper is the first one that analyzes the probabilities of false negatives and positives by developing analytical models, which take the staleness into consideration. Based on the theoretical analysis, we proposed an updating protocol that directly control the false rate. Extensive simulations validate the analytical models and prove the updating protocol to be very accurate and effective