Small Worlds, Locality, and Flooding on Landscapes
Christopher Michael Homan, Gabriel Istrate · 2003
Kleinberg provides the first theoretical characterization of the algorithmic aspects of small-world graphs embedded in metric spaces. The algorithms that Kleinberg studies are closely related to decentralized routing schemes used in ad-hoc networking environments. We study decentralized routing on fitness landscapes, which are a model that generalizes the properties of metric graphs and allows us to consider factors other than distance in designing decentralized routing schemes. We show that certain features of landscapes upper bound the amount of flooding necessary in order for greedy, decentralized routing schemes to successfully deliver messages. Finally, we show that, in Kleinberg's model, there is a phase transition in the amount of flooding necessary for efficient routing.