ProFID: practical frequent items discovery in peer-to-peer networks

Abstract

We address the problem of discovering frequent items in unstructured P2P networks which is relevant for several distributed services such as cache management, data replication, query refinement, topology optimization and security. This study makes the following contributions to the current state of the art. First, we propose and develop a fully distributed Protocol for Frequent Items Discovery (ProFID) where the result is produced at every peer. ProFID uses gossip-based (epidemic) communication, a novel pairwise averaging function and system size estimation together to discover frequent items in an unstructured P2P network. We also propose a practical rule for convergence of the algorithm. In contrast to the previous works, each peer gives a local decision for convergence based on the change of updated local state. We developed a model of ProFID in PeerSim and performed various experiments to compare and evaluate its efficiency, scalability, and applicability. The protocol's resilience under realistic churn models was studied. For evaluating the effect of network dynamics, we deployed our protocol on the Internet-scale real network PlanetLab. We also compared the accuracy and scalability of ProFID with the adaptive Push-Sum algorithm. Our results confirm the practical nature, ease of deployment and efficiency of our approach, and also show that it outperforms adaptive Push-Sum in terms of accuracy, convergence speed and message overhead.