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.