2026-07-23T07:41:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5875 2024-03-06T10:37:06Z ddc:004 open_access

A Rupestrian Algorithm Di Luna, Giuseppe A. Flocchini, Paola Prencipe, Giuseppe Santoro, Nicola Viglietta, Giovanni mobile finite-state machines self-healing distributed algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giuseppe A. Di Luna and Paola Flocchini and Giuseppe Prencipe and Nicola Santoro and Giovanni Viglietta 2016 Is Part Of LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2016.14 urn:nbn:de:0030-drops-58751 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.14 eng https://creativecommons.org/licenses/by/3.0/legalcode