Show simple item record

On the Communication Complexity of Distributed Name-Independent Routing Schemes

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierInstitut universitaire de France [IUF]
dc.contributor.authorGAVOILLE, Cyril
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorGLACET, Christian
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorHANUSSE, Nicolas
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorILCINKAS, David
dc.date.accessioned2024-04-15T09:43:14Z
dc.date.available2024-04-15T09:43:14Z
dc.date.issued2013
dc.date.conference2013-10-15
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197748
dc.description.abstractEnWe 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.sponsorshipCalculabilité et complexité en distribué - ANR-11-BS02-0014
dc.language.isoen
dc.source.titleProceedings of the 27th International Symposium on Distributed Computing
dc.subject.endistributed routing algorithm
dc.subject.enname-independent
dc.subject.encompact routing
dc.subject.enbounded stretch
dc.title.enOn the Communication Complexity of Distributed Name-Independent Routing Schemes
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
dc.description.sponsorshipEuropeExperimental UpdateLess Evolutive Routing
bordeaux.page418-432
bordeaux.volume8205
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleDISC 2013
bordeaux.countryIL
bordeaux.title.proceedingProceedings of the 27th International Symposium on Distributed Computing
bordeaux.conference.cityJérusalem
bordeaux.peerReviewedoui
hal.identifierhal-00851217
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2013-10-17
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00851217v1
bordeaux.COinSctx_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


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record