In this article we address the problem of counting the number of peers in a peer-to-peer system, and more generally of aggregating statistics of individual peers over the whole system. This functionality is useful in many applications, but hard to achieve when each node has only a limited, local knowledge of the whole system. We propose two generic techniques to solve this problem. The <i>Random Tour</i> method is based on the return time of a continuous time random walk to the node originating the query. The <i>Sample and Collide</i> method is based on counting the number of random samples gathered until a target number of redundant samples are obtained. It is inspired by the "birthday paradox" technique of 6, upon which it improves by achieving a target variance with fewer samples. The latter method relies on a sampling sub-routine which returns randomly chosen peers. Such a sampling algorithm 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. We analyse the complexity and accuracy of the two methods. We illustrate in particular how <i>expansion</i> properties of the overlay affect their performance.
%0 Conference Paper
%1 Massoulie:2006:PCS:1146381.1146402
%A Massoulié, Laurent
%A Le Merrer, Erwan
%A Kermarrec, Anne-Marie
%A Ganesh, Ayalvadi
%B Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
%C New York, NY, USA
%D 2006
%I ACM
%K counting peer random sampling walk
%P 123--132
%R 10.1145/1146381.1146402
%T Peer counting and sampling in overlay networks: random walk methods
%U http://doi.acm.org/10.1145/1146381.1146402
%X In this article we address the problem of counting the number of peers in a peer-to-peer system, and more generally of aggregating statistics of individual peers over the whole system. This functionality is useful in many applications, but hard to achieve when each node has only a limited, local knowledge of the whole system. We propose two generic techniques to solve this problem. The <i>Random Tour</i> method is based on the return time of a continuous time random walk to the node originating the query. The <i>Sample and Collide</i> method is based on counting the number of random samples gathered until a target number of redundant samples are obtained. It is inspired by the "birthday paradox" technique of 6, upon which it improves by achieving a target variance with fewer samples. The latter method relies on a sampling sub-routine which returns randomly chosen peers. Such a sampling algorithm 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. We analyse the complexity and accuracy of the two methods. We illustrate in particular how <i>expansion</i> properties of the overlay affect their performance.
%@ 1-59593-384-0
@inproceedings{Massoulie:2006:PCS:1146381.1146402,
abstract = {In this article we address the problem of counting the number of peers in a peer-to-peer system, and more generally of aggregating statistics of individual peers over the whole system. This functionality is useful in many applications, but hard to achieve when each node has only a limited, local knowledge of the whole system. We propose two generic techniques to solve this problem. The <i>Random Tour</i> method is based on the return time of a continuous time random walk to the node originating the query. The <i>Sample and Collide</i> method is based on counting the number of random samples gathered until a target number of redundant samples are obtained. It is inspired by the "birthday paradox" technique of [6], upon which it improves by achieving a target variance with fewer samples. The latter method relies on a sampling sub-routine which returns randomly chosen peers. Such a sampling algorithm 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. We analyse the complexity and accuracy of the two methods. We illustrate in particular how <i>expansion</i> properties of the overlay affect their performance.},
acmid = {1146402},
added-at = {2012-04-05T00:00:07.000+0200},
address = {New York, NY, USA},
author = {Massouli{\'e}, Laurent and Le Merrer, Erwan and Kermarrec, Anne-Marie and Ganesh, Ayalvadi},
biburl = {https://www.bibsonomy.org/bibtex/20bfbdb3e3b1dcbc3229b0b8054ed3dc3/emrahcem},
booktitle = {Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing},
description = {Peer counting and sampling in overlay networks},
doi = {10.1145/1146381.1146402},
interhash = {c01f8f8022d06db2bd1b2f565fa54c6e},
intrahash = {0bfbdb3e3b1dcbc3229b0b8054ed3dc3},
isbn = {1-59593-384-0},
keywords = {counting peer random sampling walk},
location = {Denver, Colorado, USA},
numpages = {10},
pages = {123--132},
publisher = {ACM},
series = {PODC '06},
timestamp = {2012-04-05T06:26:05.000+0200},
title = {Peer counting and sampling in overlay networks: random walk methods},
url = {http://doi.acm.org/10.1145/1146381.1146402},
year = 2006
}