Theory and Practice of Bloom Filters for Distributed Systems

TLDR

Probabilistic techniques, especially Bloom filters and their variants, are widely used in distributed systems to reduce processing and networking costs, and recent research has produced many new algorithms building on them. The article surveys basic and advanced probabilistic techniques, reviewing over 20 Bloom filter variants and their applications in caching, peer‑to‑peer systems, routing, forwarding, and data summarization. It analyzes and compares more than 20 Bloom filter variants, evaluating their suitability for distributed system components such as caching, peer‑to‑peer, routing, forwarding, and data summarization. The survey highlights the strengths and trade‑offs of each variant, illustrating how they improve performance in distributed system tasks like caching, peer‑to‑peer, routing, forwarding, and measurement data summarization.

Abstract

Many network solutions and overlay networks utilize probabilistic techniques to reduce information processing and networking costs. This survey article presents a number of frequently used and useful probabilistic techniques. Bloom filters and their variants are of prime importance, and they are heavily used in various distributed systems. This has been reflected in recent research and many new algorithms have been proposed for distributed systems that are either directly or indirectly based on Bloom filters. In this survey, we give an overview of the basic and advanced techniques, reviewing over 20 variants and discussing their application in distributed systems, in particular for caching, peer-to-peer systems, routing and forwarding, and measurement data summarization.