University of Magdeburg
Recently, 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 the authors' 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, they proposed an updating protocol that directly controls the false rate. Extensive simulations validate the analytical models and prove the updating protocol to be very accurate and effective.