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]
Leer más >
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]
< Leer menos
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Idioma
en
Communication dans un congrès
Este ítem está publicado en
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
Resumen en inglés
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 ...Leer más >
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.< Leer menos
Palabras clave en inglés
distributed routing algorithm
name-independent
compact routing
bounded stretch
Proyecto europeo
Experimental UpdateLess Evolutive Routing
Proyecto ANR
Calculabilité et complexité en distribué - ANR-11-BS02-0014
Orígen
Importado de HalCentros de investigación