A loosely synchronized gossip-based algorithm for aggregate information computation
Abstract
Many P2P applications necessitate statistics aggregate computation of certain information among all individual peers. In contrast to methods of constructing aggregation tree, centralized computing and flooding, gossip-based mechanism has the advantages of good robustness and moderate communication and computing costs. Most algorithms of this type perform aggregate computation recursively on successive time slots called rounds. They require rounds to be globally synchronous on all the nodes, which complicates the algorithm realization. To eliminate the requirement for global round synchronization, we propose a loosely synchronized algorithm to compute global statistic average based on random event triggering mechanism, and prove that the convergence time is O(logN)tau. We then propose a robust method to estimate the number of peers in the network based on this algorithm. Finally, a framework is proposed to generalize the computation of SUM, AVG, MAX, MIN, and CNT(N).