Preprint

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
License
License undefined
Identifiers
  • RERO DOC 22107
Persistent URL
https://susi.usi.ch/usi/documents/318282
Statistics

Document views: 8 File downloads:
  • ITR0902.pdf: 1