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 cc, representing a uniform random sample of size cc 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 cc; (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.

Research highlights
► Proof that uniform distribution is eventually reachable from any non-uniform distribution of nodes.
► Proof that once uniform distribution is established, any sequence of operations does not modify the previous property.
► Optimal settings are identified in term of convergence speed.