2006/05/25 by Sonali Agarwal, Ari Trachtenberg · 1 citation
Computer Science · Mathematics · #Caching and Content Delivery #Cooperative Communication and Network Coding #Mobile Ad Hoc Networks #Computer science #Gossip #Bloom filter #Heuristic #Synchronization (alternating current) #Protocol (science) #Field (mathematics) #Counting problem #Theoretical computer science #Distributed computing #Communications protocol #Computer network #Algorithm #Artificial intelligence #Mathematics
paper · doi:10.1109/itw.2006.1633815
openalex publication_date 2006/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We consider the problem of approximating the number of differences between sets held on remote hosts using minimum communication. Efficient solutions to this problem are important for streamlining a variety of communication sensitive network applications, including data synchronization in mobile networks, gossip protocols and content delivery networks. Using tools from the field of interactive communication, we show that this problem requires about as much communication as the problem of exactly determining such differences. As a result, we propose a heuristic solution based on the counting Bloom filter. We provide analytic bounds on the expected performance of our protocol and also experimental evidence that they can outperform existing difference approximation techniques.