License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.16
URN: urn:nbn:de:0030-drops-70856
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7085/
Go to the corresponding LIPIcs Volume Portal

Guerraoui, Rachid ; Maurer, Alexandre

Collision-Free Pattern Formation

pdf-format:
LIPIcs-OPODIS-2016-16.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{guerraoui_et_al:LIPIcs:2017:7085,
  author =	{Rachid Guerraoui and Alexandre Maurer},
  title =	{{Collision-Free Pattern Formation}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7085},
  URN =		{urn:nbn:de:0030-drops-70856},
  doi =		{10.4230/LIPIcs.OPODIS.2016.16},
  annote =	{Keywords: Pattern formation, Collision, Landmarks}
}

Keywords: Pattern formation, Collision, Landmarks
Collection: 20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Issue Date: 2017
Date of publication: 06.04.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI