Distributed creation and adaptation of random scale-free overlay networks
Ingo Scholtes · 2010
Random scale-free overlay topologies provide a number of properties like for example high resilience against fail-ures of random nodes, small (average) diameter as well as good expansion and congestion characteristics that make them interesting for the use in large-scale distributed sys-tems. A number of these properties have been shown to be influenced by the exponent γ of their degree distribu-tion P (k) ∝ k−γ. In this article, we present a dis-tributed rewiring scheme that is suitable to effectuate scale-free overlay topologies with an adjustable exponent. The scheme uses a biased random walk strategy to sample new endpoints of edges being rewired and relies on the equilib-rium model for scale-free networks presented in [19]. The bias of the random walk strategy can be tuned to produce random scale-free networks with arbitrary degree distribu-tion exponents greater than two. We argue that the rewiring strategy can be implemented in a distributed fashion based on a node’s information about its immediate neighbors. We present both analytical arguments as well as results that have been obtained using an implementation of the pro-posed protocol. 1.