On the Communication Complexity of Distributed Name-Independent Routing Schemes
GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Institut universitaire de France [IUF]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Institut universitaire de France [IUF]
GLACET, Christian
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Voir plus >
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Institut universitaire de France [IUF]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Institut universitaire de France [IUF]
GLACET, Christian
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
< Réduire
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Langue
en
Communication dans un congrès
Ce document a été publié dans
Proceedings of the 27th International Symposium on Distributed Computing, Proceedings of the 27th International Symposium on Distributed Computing, DISC 2013, 2013-10-15, Jérusalem. 2013, vol. 8205, p. 418-432
Résumé en anglais
We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length ...Lire la suite >
We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length of any route is stretched by a factor of at most~$7$ w.r.t. the shortest path. At any step, the memory space of each node is $\tO(\sqrt{n}\,)$. The algorithm terminates in time $O(D)$, where $D$ is the hop-diameter of $G$. In synchronous scenarios and with uniform weights, it consumes $\tO(m\sqrt{n} + n^{3/2}\min\set{D,\sqrt{n}\,})$ messages, where $m$ is the number of edges of $G$. In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is $\tO(n^{3/2})$, improves by a factor of $\sqrt{n}$ the communication complexity of \emph{any} shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.< Réduire
Mots clés en anglais
distributed routing algorithm
name-independent
compact routing
bounded stretch
Projet Européen
Experimental UpdateLess Evolutive Routing
Project ANR
Calculabilité et complexité en distribué - ANR-11-BS02-0014
Origine
Importé de halUnités de recherche