Remembering Without Memory: Tree Exploration by Asynchronous Oblivious Robots
| hal.structure.identifier | Distributed Computing Research Group [Ottawa] | |
| dc.contributor.author | FLOCCHINI, Paola | |
| 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 | ILCINKAS, David | |
| hal.structure.identifier | Département d'Informatique et d'Ingénierie [DII] | |
| dc.contributor.author | PELC, Andrzej | |
| hal.structure.identifier | School of Computer Science [Ottawa] | |
| dc.contributor.author | SANTORO, Nicola | |
| dc.date.accessioned | 2024-04-15T09:49:31Z | |
| dc.date.available | 2024-04-15T09:49:31Z | |
| dc.date.issued | 2010-03 | |
| dc.identifier.issn | 1879-2294 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198265 | |
| dc.description.abstractEn | In 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, in general, exploration cannot be done efficiently. More precisely we 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. We also prove that the size of the team used in our solution is asymptotically {\em optimal}: there are trees of degree $3$, whose exploration requires $\Omega(\frac{\log n}{\log\log n})$ robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary. | |
| dc.description.sponsorship | Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322 | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.subject.en | mobile agent | |
| dc.subject.en | robot | |
| dc.subject.en | oblivious | |
| dc.subject.en | asynchronous | |
| dc.subject.en | tree | |
| dc.subject.en | exploration | |
| dc.title.en | Remembering Without Memory: Tree Exploration by Asynchronous Oblivious Robots | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1016/j.tcs.2010.01.007 | |
| 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] | |
| bordeaux.journal | Theoretical Computer Science | |
| bordeaux.page | 1583-1598 | |
| bordeaux.volume | 411 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 14-15 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00464588 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00464588v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Theoretical%20Computer%20Science&rft.date=2010-03&rft.volume=411&rft.issue=14-15&rft.spage=1583-1598&rft.epage=1583-1598&rft.eissn=1879-2294&rft.issn=1879-2294&rft.au=FLOCCHINI,%20Paola&ILCINKAS,%20David&PELC,%20Andrzej&SANTORO,%20Nicola&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||