Improved Leader Election for Self-organizing Programmable Matter

DOI10.1007/978-3-319-72751-6_10MaRDI QIDQ5056058zbMATH OpenOpenAlexFDO

Authors Joshua J. Daymude, Robert Gmyr, Thim Strothmann, Andrea Richa, Christian Scheideler

Publication date 9 December 2022

Published in Algorithms for Sensor Systems (Search for Journal in Brave)

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

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: We consider programmable matter that consists of computationally limited devices (called particles) that are able to self-organize in order to achieve some collective goal without the need for central control or external intervention. We use the geometric amoebot model to describe such self-organizing particle systems, which defines how particles can actively move and communicate with one another. In this paper, we present an efficient local-control algorithm which solves the leader election problem in O(n) asynchronous rounds with high probability, where n is the number of particles in the system. Our algorithm relies only on local information --- particles do not have unique identifiers, any knowledge of n, or any sort of global coordinate system --- and requires only constant memory per particle.

Recommendations

• Leader election and shape formation with self-organizing programmable matter
• Distributed leader election and computation of local identifiers for programmable matter
• Deterministic Leader Election in Programmable Matter
• Shape formation by programmable particles
• Shape formation by programmable particles

Cites work

• A Markov chain algorithm for compression in self-organizing particle systems
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• An introduction to tile-based self-assembly and a survey of recent results
• Computation in networks of passively mobile finite-state sensors
• Fast algorithmic self-assembly of simple shapes using random agitation
• Improved Leader Election for Self-organizing Programmable Matter
• Intrinsic universality and the computational power of self-assembly
• Leader election and shape formation with self-organizing programmable matter
• On the computational power of DNA
• Parallel Computation Using Active Self-assembly
• The program-size complexity of self-assembled squares (extended abstract)

Cited in

(15)

• Coloring of the \(d^{\text{th}}\) power of the face-centered cubic grid
• Shape formation by programmable particles
• Building a nest by an automaton
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Leader election and shape formation with self-organizing programmable matter
• Improved Leader Election for Self-organizing Programmable Matter
• Deterministic Leader Election in Programmable Matter
• A Markov chain algorithm for compression in self-organizing particle systems
• Connected reconfiguration of lattice-based cellular structures by finite-memory robots
• 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
• Adaptive collective responses to local stimuli in anonymous dynamic networks
• Deterministic leader election for stationary programmable matter with common direction

Describes a project that uses

Uses Software

• AmoebotSim

This page was built for publication: Improved Leader Election for Self-organizing Programmable Matter

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