# GGHI13

### Summary

**Gavoille, Cyril, Glacet, Christian, Hanusse, Nicolas and Ilcinkas, David** (2013) *On the Communication Complexity of Distributed Name-Independent Routing Schemes.* In $27^{th}$ International Symposium on Distributed Computing (DISC). oct. Springer, page 12. ((URL)) (PDF)

### Abstract

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 {$\tilde{O}(\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 {$\tilde{O}(\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 {$\tilde{O}(m\sqrt{n} + n^{3/2}\min\{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 {$\tilde{O}(n^{3/2})$}, improves by a factor of {$\sqrt{n}$} the communication complexity of any shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.

### Bibtex entry

`@INPROCEEDINGS { GGHI13,`

AUTHOR = { Gavoille, Cyril and Glacet, Christian and Hanusse, Nicolas and Ilcinkas, David },

TITLE = { On the Communication Complexity of Distributed Name-Independent Routing Schemes },

BOOKTITLE = { $27^{th}$ International Symposium on Distributed Computing (DISC) },

PUBLISHER = { Springer },

LOCATION = { Jerusalem, Israel },

VOLUME = { 8205 },

SERIES = { Lecture Notes in Computer Science },

PAGES = { 12 },

MONTH = { oct },

YEAR = { 2013 },

KEYWORDS = { compact routing, distributed },

ABSTRACT = { 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 {$\tilde{O}(\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 {$\tilde{O}(\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 {$\tilde{O}(m\sqrt{n} + n^{3/2}\min\{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 {$\tilde{O}(n^{3/2})$}, improves by a factor of {$\sqrt{n}$} the communication complexity of any shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest. },

URL = { http://hal.archives-ouvertes.fr/hal-00851217/ },

PDF = { http://hal.archives-ouvertes.fr/hal-00851217/PDF/disc-12.pdf },

}