Doubly stochastic converge : uniform sampling for directed P2P networks
- Hall, Cyrus Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
- Carzaniga, Antonio Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
-
2009
18 p.
English
Uniformly sampling nodes from deployed peer-to-peer (P2P) networks has proven to be a difficult problem, as current techniques suffer from sample bias and limited applicability. A sampling service which randomly samples nodes from a uniform distribution across all members of a network offers a platform on which it is easy to construct unstructured search, data replication, and monitoring algorithms. We present an algorithm which allows for uniform random sampling, by the use of biased random walks, over the peers of any P2P network. Our algorithm, called doubly stochastic converge (DSC), iteratively adjusts the probabilities of crossing each link in the network during a random walk, such that the resulting transition matrix is doubly stochastic. DSC is fully decentralized and is designed to work on physically directed networks, allowing it to work on any P2P topology. Our simulations show that DSC converges quickly on a wide variety of topologies, and that the random walks needed for sampling are short for most topologies. In simulation studies with FreePastry [7], we show that DSC is resilient to extremely high levels of churn, while incurring a minimal sample bias.
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 22107
- ARK ark:/12658/srd1318282
- Persistent URL
- https://n2t.net/ark:/12658/srd1318282
Statistics
Document views: 26
File downloads:
- ITR0902.pdf: 45