Paper Info
Title
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 "birth- day 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
Year
DOI
Venue
2007
10.1007/s00446-007-0027-z
Distributed computing
Keywords
Field
DocType
System Size,Random Graph,Unbiased Estimator,Overlay Network,Distribute Hash Table
Birthday problem,Random graph,Random walk,Computer science,Bias of an estimator,Theoretical computer science,Sampling (statistics),Overlay,Overlay network,Technical report
Journal
Volume
Issue
ISSN
20
4
0178-2770
Citations 
PageRank 
References 
23
0.89
21
Authors
4
Name
Order
Citations
PageRank
Ayalvadi J. Ganesh1102971.65
Anne-Marie Kermarrec26649453.63
Erwan Le Merrer332223.58
Laurent Massoulié43512244.42