Peer counting and sampling in overlay networks based on random walks

Abstract : In this article, we address the problem of counting the number of peers in a peer-to-peer system. This functionality has proven useful in the design of several peer-to-peer applications. However, it is delicate to achieve when nodes are organised in an overlay network, and each node has only a limited, local knowledge of the whole system. In this paper, we propose a generic technique, called the Sample&Collide method, to solve this problem. It relies on a sampling sub-routine which returns randomly chosen peers. Such a sampling sub-routine is of independent interest. It can be used for instance for neighbour selection by new nodes joining the system. We use a continuous time random walk to obtain such samples. The core of the method consists in gathering random samples until a target number of redundant samples are obtained. This method is inspired by the “birthday paradox” technique of Bawa et al. (Estimating aggregates on a peer-to-peer network, Technical Report, Department of Computer Science, Stanford University), upon which it improves by achieving a target variance with fewer samples. We analyse the complexity and accuracy of the proposed method. We illustrate in particular how expansion properties of the overlay affect its performance. We use simulations to evaluate its performance in both static and dynamic environments with sudden changes in peer populations, and verify that it tracks varying system sizes accurately.
Type de document :
Article dans une revue
Distributed Computing, Springer Verlag, 2007, 20 (4), pp.267-278. 〈10.1007/s00446-007-0027-z〉
Liste complète des métadonnées
Contributeur : Erwan Le Merrer <>
Soumis le : vendredi 17 octobre 2008 - 10:49:51
Dernière modification le : mardi 16 janvier 2018 - 15:54:12



Erwan Le Merrer, Anne-Marie Kermarrec, Ayalvadi Ganesh, Laurent Massoulié. Peer counting and sampling in overlay networks based on random walks. Distributed Computing, Springer Verlag, 2007, 20 (4), pp.267-278. 〈10.1007/s00446-007-0027-z〉. 〈inria-00331603〉



Consultations de la notice