Mostrar el registro sencillo del ítem
On the Communication Complexity of Distributed Name-Independent Routing Schemes
hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
hal.structure.identifier | Institut universitaire de France [IUF] | |
dc.contributor.author | GAVOILLE, Cyril | |
hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
dc.contributor.author | GLACET, Christian | |
hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
dc.contributor.author | HANUSSE, Nicolas | |
hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
dc.contributor.author | ILCINKAS, David | |
dc.date.accessioned | 2024-04-15T09:43:14Z | |
dc.date.available | 2024-04-15T09:43:14Z | |
dc.date.issued | 2013 | |
dc.date.conference | 2013-10-15 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197748 | |
dc.description.abstractEn | 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. | |
dc.description.sponsorship | Calculabilité et complexité en distribué - ANR-11-BS02-0014 | |
dc.language.iso | en | |
dc.source.title | Proceedings of the 27th International Symposium on Distributed Computing | |
dc.subject.en | distributed routing algorithm | |
dc.subject.en | name-independent | |
dc.subject.en | compact routing | |
dc.subject.en | bounded stretch | |
dc.title.en | On the Communication Complexity of Distributed Name-Independent Routing Schemes | |
dc.type | Communication dans un congrès | |
dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
dc.description.sponsorshipEurope | Experimental UpdateLess Evolutive Routing | |
bordeaux.page | 418-432 | |
bordeaux.volume | 8205 | |
bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
bordeaux.institution | Université de Bordeaux | |
bordeaux.institution | Bordeaux INP | |
bordeaux.institution | CNRS | |
bordeaux.conference.title | DISC 2013 | |
bordeaux.country | IL | |
bordeaux.title.proceeding | Proceedings of the 27th International Symposium on Distributed Computing | |
bordeaux.conference.city | Jérusalem | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-00851217 | |
hal.version | 1 | |
hal.invited | non | |
hal.proceedings | oui | |
hal.conference.end | 2013-10-17 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-00851217v1 | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2027th%20International%20Symposium%20on%20Distributed%20Computing&rft.date=2013&rft.volume=8205&rft.spage=418-432&rft.epage=418-432&rft.au=GAVOILLE,%20Cyril&GLACET,%20Christian&HANUSSE,%20Nicolas&ILCINKAS,%20David&rft.genre=unknown |
Archivos en el ítem
Archivos | Tamaño | Formato | Ver |
---|---|---|---|
No hay archivos asociados a este ítem. |