Mostrar el registro sencillo del ítem

Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots

hal.structure.identifierDistributed Computing Research Group [Ottawa]
dc.contributor.authorFLOCCHINI, Paola
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorILCINKAS, David
hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorPELC, Andrzej
hal.structure.identifierSchool of Computer Science [Ottawa]
dc.contributor.authorSANTORO, Nicola
dc.contributor.editorAlexander A. Shvartsman, Pascal Felber
dc.date.accessioned2024-04-15T09:53:45Z
dc.date.available2024-04-15T09:53:45Z
dc.date.issued2008-06
dc.date.conference2008-06
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198625
dc.description.abstractEnIn the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is {\sc Asynch} where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of {\em exploration}: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that there are $n$-node trees where $\Omega(n)$ robots are necessary; this holds even if the maximum degree is $4$. On the other hand, we show that if the maximum degree is $3$, it is possible to explore with only $O(\frac{\log n} {\log\log n})$ robots. The proof of the result is constructive. Finally, we prove that the size of the team is asymptotically {\em optimal}: we show that there are trees of degree $3$ whose exploration requires $\Omega(\frac{\log n}{\log\log n})$ robots.
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 15th International Colloquium on Structural Information and Communication Complexity
dc.subject.enmobile agent
dc.subject.enrobot
dc.subject.enoblivious
dc.subject.enasynchronous
dc.subject.enexploration
dc.title.enRemembering without Memory: Tree Exploration by Asynchronous Oblivious Robots
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-540-69355-0_5
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page33-47
bordeaux.volume5058
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleSIROCCO 2008
bordeaux.countryCH
bordeaux.title.proceedingProceedings of the 15th International Colloquium on Structural Information and Communication Complexity
bordeaux.conference.cityVillars-sur-Ollon
bordeaux.peerReviewedoui
hal.identifierhal-00341465
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00341465v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2015th%20International%20Colloquium%20on%20Structural%20Information%20and%20Communication%20Complexity&rft.date=2008-06&rft.volume=5058&rft.spage=33-47&rft.epage=33-47&rft.au=FLOCCHINI,%20Paola&ILCINKAS,%20David&PELC,%20Andrzej&SANTORO,%20Nicola&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem