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. © Giuseppe A. Di Luna, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta.
A rupestrian algorithm / Di Luna, G; Flocchini, P; Prencipe, G; Santoro, N; Viglietta, G. - (2016). (Intervento presentato al convegno 8th International Conference on Fun with Algorithms, FUN 2016 tenutosi a La Maddalena; Italy; 8 June 2016 through 10 June 2016; Code 121954) [10.4230/LIPIcs.FUN.2016.14].
A rupestrian algorithm
Di Luna G
;
2016
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. © Giuseppe A. Di Luna, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta.| File | Dimensione | Formato | |
|---|---|---|---|
|
DiLuna_A-rupestrian-algorithm_2016.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
958.98 kB
Formato
Adobe PDF
|
958.98 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
