Afficher la notice abrégée

Synchronous Rendezvous for Location-Aware Agents

hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorCOLLINS, Andrew
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.authorKOSOWSKI, Adrian
hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorRUSSELL, Martin
dc.contributor.editorDavid Peleg
dc.date.accessioned2024-04-15T09:46:34Z
dc.date.available2024-04-15T09:46:34Z
dc.date.issued2011-09-19
dc.date.conference2011-09-20
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198019
dc.description.abstractEnWe study rendezvous of two anonymous agents, where each agent knows its own initial position in the environment. Their task is to meet each other as quickly as possible. The time of the rendezvous is measured by the number of synchronous rounds that agents need to use in the worst case in order to meet. In each round, an agent may make a simple move or it may stay motionless. We consider two types of environments, finite or infinite graphs and Euclidean spaces. A simple move traverses a single edge (in a graph) or at most a unit distance (in Euclidean space). The rendezvous consists in visiting by both agents the same point of the environment simultaneously (in the same round). In this paper, we propose several asymptotically optimal rendezvous algorithms. In particular, we show that in the line and trees as well as in multi-dimensional Euclidean spaces and grids the agents can rendezvous in time O(d), where d is the distance between the initial positions of the agents. The problem of location-aware rendezvous was studied before in the asynchronous model for Euclidean spaces and multi-dimensional grids, where the emphasis was on the length of the adopted rendezvous trajectory. We point out that, contrary to the asynchronous case, where the cost of rendezvous is dominated by the size of potentially large neighborhoods, the agents are able to meet in all graphs of at most n nodes in time almost linear in d, namely, O(d log^2 n). We also determine an infinite family of graphs in which synchronized rendezvous takes time Ω(d).
dc.language.isoen
dc.publisherSpringer
dc.title.enSynchronous Rendezvous for Location-Aware Agents
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-24100-0_42
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page447-459
bordeaux.volume6950
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleDISC 2011 - 25th International Symposium on Distributed Computing
bordeaux.countryIT
bordeaux.conference.cityRome
bordeaux.peerReviewedoui
hal.identifierhal-00646907
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2011-09-22
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00646907v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2011-09-19&rft.volume=6950&rft.spage=447-459&rft.epage=447-459&rft.au=COLLINS,%20Andrew&CZYZOWICZ,%20Jurek&GASIENIEC,%20Leszek&KOSOWSKI,%20Adrian&RUSSELL,%20Martin&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