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.FUN.2016.14
URN: urn:nbn:de:0030-drops-58751
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5875/
Di Luna, Giuseppe A. ;
Flocchini, Paola ;
Prencipe, Giuseppe ;
Santoro, Nicola ;
Viglietta, Giovanni
A Rupestrian Algorithm
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 |
|
Collection: |
|
8th International Conference on Fun with Algorithms (FUN 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
02.06.2016 |
