Back to Search
Start Over
On the Communication Complexity of Distributed Name-Independent Routing Schemes
- Source :
- Proceedings of the 27th International Symposium on Distributed Computing, DISC 2013, DISC 2013, Oct 2013, Jérusalem, Israel. pp.418-432, Lecture Notes in Computer Science ISBN: 9783642415265, DISC
- Publication Year :
- 2013
- Publisher :
- HAL CCSD, 2013.
-
Abstract
- International audience; 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.
- Subjects :
- TheoryofComputation_MISCELLANEOUS
distributed routing algorithm
compact routing
Routing table
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
020206 networking & telecommunications
[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
02 engineering and technology
bounded stretch
01 natural sciences
Combinatorics
Asynchronous algorithms
010201 computation theory & mathematics
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
Shortest path problem
0202 electrical engineering, electronic engineering, information engineering
[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Graph (abstract data type)
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Communication complexity
name-independent
Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-642-41526-5
- ISBNs :
- 9783642415265
- Database :
- OpenAIRE
- Journal :
- Proceedings of the 27th International Symposium on Distributed Computing, DISC 2013, DISC 2013, Oct 2013, Jérusalem, Israel. pp.418-432, Lecture Notes in Computer Science ISBN: 9783642415265, DISC
- Accession number :
- edsair.doi.dedup.....d0f4397ea8c0c6b292c485cda0d073eb