Biased Selection for Building Small-World Networks

Date Added: Oct 2010
Format: PDF

Small-world networks are currently present in many distributed applications and can be built augmenting a base network with long-range links using a probability distribution. Currently available distributed algorithms to select these long-range neighbors are designed ad hoc for specific probability distributions. In this paper, the authors propose a new algorithm called Biased Selection (BS) that, using a uniform sampling service (that could be implemented with, for instance, a gossip-based protocol), allows to select long-range neighbors with any arbitrary distribution in a distributed way. This algorithm is of iterative nature and has a parameter r that gives its number of iterations. They prove that the obtained sampling distribution converges to the desired distribution as r grows.