A fully distributed scheme to run a network into a small world
Résumé
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.
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 sila métrique du graphe considéré est à croissance bornée, en ajoutant un seul arc (aléatoire) par nœud, 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.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...