A Formal Characterization of Uniform Peer Sampling Based on View Shuffling

摘要

Consider a group of peers, an ideal random peer sampling service should return a peer, which is an unbiased independent random sample of the group. This paper focuses on peer sampling service based on view shuffling (aka gossip-based peer sampling), where each peer is equipped with a local view of size c. This view should correspond to a uniform random sample of size c of the whole system in order to implement correctly a uniform peer sampling service. To this aim, pairs of peers regularly and continuously swap a part of their local views (shuffling operation). The paper provides a proof that (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 and (ii) once previous property holds, any successive sequence of shuffle operations does not modify this uniformity property. This paper also presents some numerical results concerning the speed of convergence to uniform samples of the local views.