License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.14
URN: urn:nbn:de:0030-drops-58751
URL: http://drops.dagstuhl.de/opus/volltexte/2016/5875/
Go to the corresponding LIPIcs Volume Portal


Di Luna, Giuseppe A. ; Flocchini, Paola ; Prencipe, Giuseppe ; Santoro, Nicola ; Viglietta, Giovanni

A Rupestrian Algorithm

pdf-format:
15.pdf (0.9 MB)


Abstract

Deciphering recently discovered cave paintings by the Astracinca, an egalitarian leaderless society flourishing in the 3rd millennium BCE, we present and analyze their shamanic ritual for forming new colonies. This ritual can actually be used by systems of anonymous mobile finite-state computational entities located and operating in a grid to solve the line recovery problem, a task that has both self-assembly and flocking requirements. The protocol is totally decentralized, fully concurrent, provably correct, and time optimal.

BibTeX - Entry

@InProceedings{diluna_et_al:LIPIcs:2016:5875,
  author =	{Giuseppe A. Di Luna and Paola Flocchini and Giuseppe Prencipe and Nicola Santoro and Giovanni Viglietta},
  title =	{{A Rupestrian Algorithm}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Erik D. Demaine and Fabrizio Grandoni},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5875},
  URN =		{urn:nbn:de:0030-drops-58751},
  doi =		{10.4230/LIPIcs.FUN.2016.14},
  annote =	{Keywords: mobile finite-state machines, self-healing distributed algorithms}
}

Keywords: mobile finite-state machines, self-healing distributed algorithms
Seminar: 8th International Conference on Fun with Algorithms (FUN 2016)
Issue Date: 2016
Date of publication: 25.05.2016


DROPS-Home | Fulltext Search | Imprint Published by LZI