On the Uniformity of Peer Sampling based on View Shuffling

Abstract : Consider a group of peers, an ideal random peer sampling service should return a peer, which is a uniform independent random sample of the group. This paper focuses on the implementation and analysis of a peer sampling service based on symmetric view shuffling, where each peer is equipped with a local view of size c, representing a uniform random sample of size c of the whole system. To this end, pairs of peers regularly and continuously swap a part of their local views (shuffle operation). The paper provides the following formal proofs: (i) starting from any non-uniform distribution of peers in the peers' local views, after a sequence of pairwise shuffle operations, each local view eventually represents a uniform sample of size c; (ii) once previous property holds, any successive sequence of shuffle operations does not modify this uniformity property and (iii) a lower bound for convergence speed. This paper also presents some numerical results concerning the speed of convergence to uniform samples of the local views.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2011, 71 (8), pp.1165-1176. 〈10.1016/j.jpdc.2011.01.009〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00559003
Contributeur : Yann Busnel <>
Soumis le : lundi 24 janvier 2011 - 15:53:50
Dernière modification le : jeudi 11 janvier 2018 - 06:22:48

Identifiants

Collections

Citation

Yann Busnel, Roberto Beraldi, Roberto Baldoni. On the Uniformity of Peer Sampling based on View Shuffling. Journal of Parallel and Distributed Computing, Elsevier, 2011, 71 (8), pp.1165-1176. 〈10.1016/j.jpdc.2011.01.009〉. 〈inria-00559003〉

Partager

Métriques

Consultations de la notice

211