On the uniformity of peer sampling based on view shuffling

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 the 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. (C) 2011 Elsevier Inc. All rights reserved.