Skip to Main content Skip to Navigation

Ensuring Uniformity in Random Peer Sampling Services

Anne-Marie Kermarrec 1 Vincent Leroy 1 Christopher Thraves-Caro 1 
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : The peer sampling service is a core building block for gossip protocols in peer-to-peer networks. Ideally, a peer sampling service continuously provides each peer with a sample of peers picked uniformly at random in the network. While empirical studies have shown that uniformity was achieved, analysis proposed so far assume strong restrictions on the topology of the overlay network it continuously generates. In this work, we analyze a Generic Random Peer Sampling Service (GRPS) that satisfies the desirable properties for any peer sampling service –small views, uniform sample, load balancing, and independence– and relieve strong degree connections in the nodes assumed in previous works. The main result we prove is: starting from any simple (without loops and parallel edges) directed graph with out-degree equal to c for all nodes, and recursively applying GRPS, eventually results in a random simple directed graph with out-degree equal to c for all nodes. We test empirically convergence time and independence time for GRPS. We use this empirical evaluation to show that GRPS performs better than previously presented peer sampling services. We also present a variant of GRPS that ensures that the in and out-degrees of nodes in the initial network are maintained in the resulting graph. Finally, we discuss on how to deal with new nodes in both settings.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Chrsitopher Thraves Caro Connect in order to contact the contributor
Submitted on : Thursday, April 29, 2010 - 6:10:39 PM
Last modification on : Thursday, January 20, 2022 - 4:19:58 PM
Long-term archiving on: : Monday, October 22, 2012 - 3:31:44 PM


Files produced by the author(s)


  • HAL Id : inria-00477658, version 1


Anne-Marie Kermarrec, Vincent Leroy, Christopher Thraves-Caro. Ensuring Uniformity in Random Peer Sampling Services. [Research Report] 2010. ⟨inria-00477658⟩



Record views


Files downloads