Technical report detail

Doubly Stochastic Converge: Uniform Sampling for Directed P2P Networks

by Cyrus Hall and Antonio Carzaniga

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, we show that DSC is resilient to extremely high levels of churn, while incurring a minimal sample bias.

Technical report 2009/02, January 2009

BibTex entry

@techreport{09doubly, author = {Cyrus Hall and Antonio Carzaniga}, title = {Doubly Stochastic Converge: Uniform Sampling for Directed P2P Networks}, institution = {University of Lugano}, number = {2009/02}, year = 2009, month = jan }