Non-uniform Random Membership Management in Peer-to-Peer Networks
Ming Zhong, Kai Shen, and Joel Seiferas
Department of Computer Science, University of Rochester
Existing random membership management algorithms provide each node with a small,
uniformly random subset of global participants. However, many applications would
benefit more from non-uniform random member subsets. For instance, non-uniform
gossip algorithms can provide distance-based propagation bounds and thus
information can reach nearby nodes sooner. In another example, Kleinberg shows
that networks with random long-links following distance-based non-uniform
distributions exhibit better routing performance than those with uniformly
randomized topologies. In this paper, we propose a scalable non-uniform random
membership management algorithm, which provides each node with a random membership
subset with application-specified probability distributions---e.g., with
probability inversely proportional to distances. Our algorithm is the first
non-uniform random membership management algorithm with proved convergence and
bounded convergence time. Moreover, our algorithm does not put specific
restrictions on the network topologies and thus have wide applicability.