Probabilistic Algorithms

Many peer-to-peer (P2P) protocols and overlay networks utilize probabilistic techniques to reduce processing and networking costs. This chapter 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 network solutions.