Channel aware folding cuts data traffic in distributed systems
Channel-Aware Selection of Folded Bloom Filters for Distributed Systems
Information TheoryCryptography and SecurityNetworking and Internet Architecture
Summary
Sending large sets of data in distributed systems can use a lot of communication resources. The authors study special methods that shrink this data, called folded Bloom filters, which trade some accuracy for smaller size. They develop a way to choose the best-sized data version based on current network conditions, keeping the data fresh and reducing communication costs. Tests on phishing URL data and different network scenarios showed this approach can work better than traditional fixed-size or fully lossless methods.
What this means in practice
- •For distributed system engineers: Optimize data transmission sizes adaptively to current network conditions to reduce overhead and keep data up to date.
- •For network protocol developers: Improve messaging efficiency by selecting compressed membership filters suited for varying communication channels in distributed networks.
Authors
John Cartmell, Mihaela Cardei, Ionut Cardei
Abstract
Periodic Bloom-filter transmission can impose substantial overhead in communication-constrained distributed systems. Lossless compression preserves membership behavior but provides a single transmission size, whereas established OR folding produces smaller representations with higher false-positive rates (FPRs) while preserving the no-false-negative property. This paper investigates channel-aware selection among OR-folded representations. The sender retains an unchanged canonical filter, constructs a catalog satisfying a maximum FPR, and selects the FPR-qualified representation with the largest retained length supported by the communication resources available at each reporting opportunity. Unlike folding driven principally by cardinality and false-positive constraints, selection is driven by time-varying communication conditions. Using two phishing URL datasets, the framework is evaluated under Five-State Markov Capacity, Gilbert--Elliott burst-error, and Rayleigh block-fading models. Channel-aware folding improves communication efficiency and receiver freshness relative to complete-filter and lossless-compression baselines when communication opportunities vary substantially. Under the more favorable Gilbert--Elliott model, it remains competitive in efficiency while maintaining the freshest receiver state. These results show that FPR-qualified folded views provide useful transmission operating points when a recent lower-fidelity update is preferable to delaying a larger representation.