Skip to Main content Skip to Navigation

A fully distributed scheme to run a network into a small world

Abstract : We investigate the problem of efficiently preprocessing a large network, in afully distributed manner, so that the resulting network is a navigable smallworld. Namely, if the network has bounded growth, by adding a single entry ina distributed manner to each routing table (using O(n) rounds and O(polylog n)space), we obtain a network in which the greedy routing algorithm computespaths of polylogarithmic expected length between any pair of nodes. A boundedgrowth graph is a graph of constant expansion rate, i.e. the number of nodeswithin distance 2r from a given node is at most a constant times the number ofnodes within distance r. These graphs are considered as a relevant frameworkfor real networks as Peer-to-peer networks where our scheme could be usedto considerably improve the routing speed over time. We also extends ouralgorithm to graphs of polylogarithmic expansion rate. Recent small worldmodels provide augmentation processes of large graph classes into navigablesmall worlds via the addition of new random links to each node. However,the computation of the required random links distribution kept these processesunrealistic for large decentralized networks. Our algorithm, based on a carefulsampling of a set of leader nodes, bypasses these limitations.
Document type :
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 10:40:24 AM
Last modification on : Tuesday, December 1, 2020 - 5:54:03 PM


Files produced by the author(s)


  • HAL Id : hal-02102237, version 1



Philippe Duchon, Nicolas Hanusse, Emmanuelle Lebhar, Nicolas Schabanel. A fully distributed scheme to run a network into a small world. [Research Report] LIP RR-2006-03, Laboratoire de l'informatique du parallélisme. 2006, 2+13p. ⟨hal-02102237⟩



Record views


Files downloads