2026-08-18T13:25:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10716 2024-03-06T10:46:32Z ddc:004 open_access

Deterministic Leader Election in Programmable Matter Emek, Yuval Kutten, Shay Lavi, Ron Moses Jr., William K. programmable matter geometric amoebot model leader election Addressing a fundamental problem in programmable matter, we present the first deterministic algorithm to elect a unique leader in a system of connected amoebots assuming only that amoebots are initially contracted. Previous algorithms either used randomization, made various assumptions (shapes with no holes, or known shared chirality), or elected several co-leaders in some cases. Some of the building blocks we introduce in constructing the algorithm are of interest by themselves, especially the procedure we present for reaching common chirality among the amoebots. Given the leader election and the chirality agreement building block, it is known that various tasks in programmable matter can be performed or improved. The main idea of the new algorithm is the usage of the ability of the amoebots to move, which previous leader election algorithms have not used. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuval Emek and Shay Kutten and Ron Lavi and William K. Moses Jr. 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.140 urn:nbn:de:0030-drops-107169 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.140 eng https://creativecommons.org/licenses/by/3.0/legalcode