Afficher la notice abrégée

Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBAMPAS, Evangelos
hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorCZYZOWICZ, Jurek
hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorGASIENIEC, Leszek
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorILCINKAS, David
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorLABOUREL, Arnaud
dc.date.accessioned2024-04-15T09:48:51Z
dc.date.available2024-04-15T09:48:51Z
dc.date.issued2010-09
dc.date.conference2010-09
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198206
dc.description.abstractEnTwo anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension $\dime > 0$, starting from two arbitrary positions at distance at most $d$. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a $\dime$-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length $O(d^\dime{\rm polylog\ }d)$. This bound for the case of {\sc 2d}~-grids subsumes the main result of \cite{CCGL}. The algorithm is almost optimal, since the $\Omega(d^\dime)$ lower bound is straightforward. Further, we apply our rendezvous method to the following network design problem. The ports of the $\dime$-dimensional grid have to be set such that two anonymous agents starting at distance at most $d$ from each other will always meet, moving in an asynchronous manner, after traversing a $O(d^\dime{\rm polylog\ }d)$ length trajectory. We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the $\dime$-dimensional Euclidean space. The agents have the radii of visibility of $r_1$ and $r_2$, respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of $O((\frac{d}{r})^\dime {\rm polylog}(\frac{d}{r}))$, where $r = \min(r_1, r_2)$ and for $r\geq 1$.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Berlin / Heidelberg
dc.source.titleProceedings of the 24th International Symposium on Distributed Computing
dc.subjectmobile agents
dc.subjectrendezvous
dc.title.enAlmost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-15763-9_28
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page297--311
bordeaux.volume6343
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleDISC 2010
bordeaux.countryUS
bordeaux.title.proceedingProceedings of the 24th International Symposium on Distributed Computing
bordeaux.peerReviewedoui
hal.identifierhal-00534263
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00534263v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2024th%20International%20Symposium%20on%20Distributed%20Computing&rft.date=2010-09&rft.volume=6343&rft.spage=297--311&rft.epage=297--311&rft.au=BAMPAS,%20Evangelos&CZYZOWICZ,%20Jurek&GASIENIEC,%20Leszek&ILCINKAS,%20David&LABOUREL,%20Arnaud&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée