Gossip-based distribution estimation in peer-to-peer networks

Abstract

We propose a novel gossip-based technique that allows each node in a system to estimate the distribution of values held by other nodes. We observe that the presence of duplicate values does not significantly affect the distribution of values in samples collected through gossip, and based on that explore different data synopsis techniques that optimize space and time while allowing nodes to accumulate information. Unlike previous aggregation schemes, our approach focuses on allowing all nodes in the system to compute an estimate of the entire distribution in a decentralized and efficient manner. We evaluate our approach through simulation, showing that it is simple and scalable, and that it allows all nodes in the system to converge to a satisfactory estimate of the distribution in a small number of rounds.