New interface

# Exclusive perpetual ring exploration without chirality

3 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
4 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : In this paper, we study the exclusive perpetual exploration problem with mobile anonymous and oblivious robots in a discrete space. Our results hold for the most generic settings: robots are asynchronous and are not given any sense of direction, so the left and right sense (\emph{i.e.} chirality) is decided by the adversary that schedules robots for execution, and may change between invocations of a particular robots (as robots are oblivious). We investigate both the minimal and the maximal number of robots that are necessary and sufficient to solve the exclusive perpetual exploration problem. On the minimal side, we prove that three deterministic robots are necessary and sufficient, provided that the size $n$ of the ring is at least $10$, and show that no protocol with three robots can exclusively perpetually explore a ring of size less than $10$. On the maximal side, we prove that $k=n-5$ robots are necessary and sufficient to exclusively perpetually explore a ring of size $n$ when $n$ is co-prime with $k$.
Keywords :
Document type :
Reports (Research report)
Domain :

Cited literature [8 references]

https://hal.inria.fr/inria-00464206
Contributor : Maria Potop-Butucaru Connect in order to contact the contributor
Submitted on : Tuesday, March 16, 2010 - 2:14:41 PM
Last modification on : Friday, November 25, 2022 - 7:04:09 PM
Long-term archiving on: : Friday, October 19, 2012 - 10:00:19 AM

### File

perpetual-last.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00464206, version 1

### Citation

Lélia Blin, Alessia Milani, Maria Potop-Butucaru, Sébastien Tixeuil. Exclusive perpetual ring exploration without chirality. [Research Report] Université d'Evry Val d'Essonne. 2010, pp.17. ⟨inria-00464206⟩

Record views