Skip to Main content Skip to Navigation
Reports

Leader Election Problem Versus Pattern Formation Problem

Abstract : Leader election and arbitrary pattern formation are fundammental tasks for a set of au- tonomous mobile robots. The former consists in distinguishing a unique robot, called the leader. The latter aims in arranging the robots in the plane to form any given pattern. The solvability of both these tasks turns out to be necessary in order to achieve more complex tasks. In this paper, we study the relationship between these two tasks in a model, called CORDA, wherein the robots are weak in several aspects. In particular, they are fully asynchronous and they have no direct means of communication. They cannot remember any previous observation nor computation performed in any previous step. Such robots are said to be oblivious. The robots are also uniform and anonymous, i.e, they all have the same program using no global parameter (such that an identity) allowing to differentiate any of them. Moreover, none of them share any kind of common coordinate mechanism or common sense of direction, except that they agree on a common handedness (chirality). In such a system, Flochini et al. proved in [9] that it is possible to solve the leader election problem for n ≥ 3 robots if the arbitrary pattern formation is solvable for n ≥ 3. In this paper, we show that the converse is true for n ≥ 4 and thus, we deduce that both problems are equivalent for n ≥ 4 in CORDA provided the robots share the same chirality. The possible equivalence for n = 3 remains an open problem in CORDA.
Document type :
Reports
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00361916
Contributor : Yoann Dieudonné <>
Submitted on : Tuesday, October 20, 2009 - 2:29:46 PM
Last modification on : Tuesday, April 27, 2021 - 3:37:59 PM
Long-term archiving on: : Wednesday, September 22, 2010 - 1:23:23 PM

Files

leader.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00361916, version 2
  • ARXIV : 0902.2851

Citation

Yoann Dieudonné, Franck Petit, Vincent Villain. Leader Election Problem Versus Pattern Formation Problem. [Research Report] 2009. ⟨inria-00361916v2⟩

Share

Metrics

Record views

204

Files downloads

752