NDLI: Peer counting and sampling in overlay networks based on random walks

Please wait, while we are loading the content...

Peer counting and sampling in overlay networks based on random walks

Content Provider	Springer Nature Link
Author	Ganesh, A. J. Kermarrec, A. M. Merrer, E. Massoulié, L.
Copyright Year	2007
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.
Starting Page	267
Ending Page	278
Page Count	12
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	20
Issue Number	4
e-ISSN	14320452
Language	English
Publisher	Springer-Verlag
Publisher Date	2007-06-05
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Theory of Computation Software Engineering/Programming and Operating Systems Computer Systems Organization and Communication Networks Computer Hardware Computer Communication Networks
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

HyperTree for self-stabilizing peer-to-peer systems

On the establishment of distinct identities in overlay networks

Towards worst-case churn resistant peer-to-peer systems

Building scalable and robust peer-to-peer overlay networks for broadcasting using network coding

Fast message dissemination in random geometric networks

Approximate distributed top-k queries

Sequentially consistent versus linearizable counting networks

Oblivious signature-based envelope

A knowledge-based analysis of global function computation

Peer counting and sampling in overlay networks based on random walks

Similar Documents

HyperTree for self-stabilizing peer-to-peer systems

On the establishment of distinct identities in overlay networks

Towards worst-case churn resistant peer-to-peer systems

Building scalable and robust peer-to-peer overlay networks for broadcasting using network coding

Fast message dissemination in random geometric networks

Approximate distributed top-k queries

Sequentially consistent versus linearizable counting networks

Oblivious signature-based envelope

A knowledge-based analysis of global function computation

Peer counting and sampling in overlay networks based on random walks