Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Collision-Free Pattern Formation
 
conference paper not in proceedings

Collision-Free Pattern Formation

Guerraoui, Rachid  
•
Maurer, Alexandre David Olivier  
2016
OPODIS 2016

Shoals of small fishes can change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. In this paper, we study the analog problem of distributed pattern formation. A set of processes needs to move from a set of initial positions to a set of final positions. The processes are oblivious (no internal memory) and must preserve, at any time, a minimal distance between them. A naive solution would be to move the processes one by one, but this would take too long. The difficulty here is to move the processes simultaneously in clearly delimited phases, no matter how unfavorable the initial configuration may be. We solve this by treating the problem ``dimension by dimension'': the processes first form 1D trails, then gather into a 2D shape (this technique can be generalized to higher dimensions). We present an optimal algorithm which time complexity depends linearly on the radius of the smallest circle containing both initial and final positions. The algorithm is self-stabilizing, as the processes are oblivious and the initial positions are arbitrary.

  • Files
  • Details
  • Metrics
Type
conference paper not in proceedings
Author(s)
Guerraoui, Rachid  
•
Maurer, Alexandre David Olivier  
Date Issued

2016

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event name
OPODIS 2016
Available on Infoscience
June 29, 2017
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/138672
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés