Deterministic Leader Election in Programmable Matter

DOI10.4230/LIPICS.ICALP.2019.140MaRDI QIDQ5092343zbMATH OpenOpenAlexFDO

Authors Yuval Emek, Shay Kutten, Ron Lavi, William K. jun. Moses

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1905.00580

zbMATH Keywords

geometric amoebot modelleader electionprogrammable matter

Mathematics Subject Classification ID

Distributed systems (68M14) Other nonclassical models of computation (68Q09) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms (68W40)

Abstract: 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.

Recommendations

• Improved Leader Election for Self-organizing Programmable Matter
• Distributed leader election and computation of local identifiers for programmable matter
• Leader election and shape formation with self-organizing programmable matter
• scientific article; zbMATH DE number 6313182
• Algorithms for leader election by cellular automata
• Leader election in asynchronous distributed systems

Cites work

• A Markov chain algorithm for compression in self-organizing particle systems
• Distributed network protocols
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Improved Leader Election for Self-organizing Programmable Matter
• Leader election and shape formation with self-organizing programmable matter
• Shape formation by programmable particles
• Universal coating for programmable matter

Cited in

(8)

• Leader election and shape formation with self-organizing programmable matter
• Improved Leader Election for Self-organizing Programmable Matter
• Distributed leader election and computation of local identifiers for programmable matter
• The canonical amoebot model: algorithms and concurrency control
• Efficient Deterministic Leader Election for Programmable Matter
• Stationary and deterministic leader election in self-organizing particle systems
• Deterministic self-stabilising leader election for programmable matter with constant memory
• Deterministic leader election for stationary programmable matter with common direction

This page was built for publication: Deterministic Leader Election in Programmable Matter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092343)