Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots
| hal.structure.identifier | School of Electrical Engineering and Computer Science [EECS] | |
| 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:42:19Z | |
| dc.date.available | 2024-04-15T09:42:19Z | |
| dc.date.issued | 2013-03 | |
| dc.identifier.issn | 0178-4617 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197671 | |
| dc.description.abstractEn | We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimensional plane, but (with one exception) has not been investigated before for networks. Our results imply that, although these weak capabilities of robots render the problem considerably more difficult, ring exploration by a small team of robots is still possible. We first show that, when k and n are not co-prime, the problem is not solvable in general, e.g., if k divides n there are initial placements of the robots for which gathering is impossible. We then prove that the problem is always solvable provided that n and k are co-prime, for k >= 17, by giving an exploration algorithm that always terminates, starting from arbitrary initial configurations. Finally, we consider the minimum number rho(n) of robots that can explore a ring of size n. As a consequence of our positive result we show that rho(n) is O(log n). We additionally prove that Omega(log n) robots are necessary for infinitely many n. | |
| dc.language.iso | en | |
| dc.publisher | Springer Verlag | |
| dc.subject.en | mobile robots | |
| dc.subject.en | asynchronous | |
| dc.subject.en | oblivious | |
| dc.subject.en | exploration | |
| dc.subject.en | ring | |
| dc.title.en | Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1007/s00453-011-9611-5 | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| bordeaux.journal | Algorithmica | |
| bordeaux.page | 562-583 | |
| bordeaux.volume | 65 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 3 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00912499 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00912499v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Algorithmica&rft.date=2013-03&rft.volume=65&rft.issue=3&rft.spage=562-583&rft.epage=562-583&rft.eissn=0178-4617&rft.issn=0178-4617&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. |
|||