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

Abstract

(eng) We investigate the problem of efficiently preprocessing a large network, in a fully distributed manner, so that the resulting network is a navigable small world. Namely, if the network has bounded growth, by adding a single entry in a 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 computes paths of polylogarithmic expected length between any pair of nodes. A bounded growth graph is a graph of constant expansion rate, i.e. the number of nodes within distance 2r from a given node is at most a constant times the number of nodes within distance r. These graphs are considered as a relevant framework for real networks as Peer-to-peer networks where our scheme could be used to considerably improve the routing speed over time. We also extends our algorithm to graphs of polylogarithmic expansion rate. Recent small world models provide augmentation processes of large graph classes into navigable small worlds via the addition of new random links to each node. However, the computation of the required random links distribution kept these processes unrealistic for large decentralized networks. Our algorithm, based on a careful sampling of a set of leader nodes, bypasses these limitations. (fre) Nous abordons le problème de l’augmentation d’un graphe en un petit monde navigable de façon efficace et distribuée. Précisément, nous montrons que si la métrique du graphe considéré est à croissance bornée, en ajoutant un seul arc (aléatoire) par noeud, on obtient un graphe où l’algorithme de routage glouton calcule des chemins de longueur d’espérance polylogarithmique en la taille du graphe, entre toutes les paires de sommets. Cette opération se fait de façon distribuée, en O(n) rondes avec une mémoire polylogarithmique. Les métriques à croissances bornées sont les métriques telles que la taille d’une boule de rayon 2r est au plus une constante fois la taille de la boule de même centre et de rayon r. Elles sont actuellement considérées comme un cadre réaliste pour les grands réseaux décentralisés, comme les réseaux pair-à-pair. Les modèles de petits mondes proposés récemment donnent des processus d’augmentation de graphes en petits mondes navigables, par l’ajout d’arcs aléatoires supplémentaires. Toutefois, le calcul de la distribution de ces nouveaux liens aléatoire nécessite, grossièrement, la connaissance de la totalité de la métrique, rendant ces processus d’augmentations non réalistes pour un grand réseau distribué. En utilisant un échantillonnage aléatoire des sommets bien choisi, notre algorithme d’augmentation parvient à dépasser ces limitations.