Leader election and shape formation with self-organizing programmable matter
From MaRDI portal
Publication:2948412
DOI10.1007/978-3-319-21999-8_8zbMATH Open1404.68045arXiv1503.07991OpenAlexW1632525963MaRDI QIDQ2948412FDOQ2948412
Authors: Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andrea Richa, Christian Scheideler 
Publication date: 30 September 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: We consider programmable matter consisting of simple computational elements, called particles, that can establish and release bonds and can actively move in a self-organized way, and we investigate the feasibility of solving fundamental problems relevant for programmable matter. As a suitable model for such self-organizing particle systems, we will use a generalization of the geometric amoebot model first proposed in SPAA 2014. Based on the geometric model, we present efficient local-control algorithms for leader election and line formation requiring only particles with constant size memory, and we also discuss the limitations of solving these problems within the general amoebot model.
Full work available at URL: https://arxiv.org/abs/1503.07991
Recommendations
Cites Work
- An introduction to tile-based self-assembly and a survey of recent results
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor (extended abstract)
- On the computational power of DNA
- Computation in networks of passively mobile finite-state sensors
- Distributed computing by mobile robots: gathering
- Intrinsic universality and the computational power of self-assembly
- On the computational power of oblivious robots
- Memory-efficient and self-stabilizing network RESET (extended abstract)
- Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
- Local spreading algorithms for autonomous robot systems
- Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
- Computing without communicating: ring exploration by asynchronous oblivious robots
- A distributed algorithm for gathering many fat mobile robots in the plane
- Fast algorithmic self-assembly of simple shapes using random agitation
- Parallel Computation Using Active Self-assembly
- On the convergence of the Hegselmann-Krause system
- \textit{Physarum} can compute shortest paths
- Natural algorithms
- Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles
- Distributed reconfiguration of metamorphic robot chains
- Uniform scattering of autonomous mobile robots in a grid
Cited In (24)
- Tilt assembly: algorithms for micro-factories that build objects with uniform external forces
- The Synergy of Finite State Machines
- Deterministic Leader Election in Programmable Matter
- Title not available (Why is that?)
- CADbots: algorithmic aspects of manipulating programmable matter with finite automata
- Distributed leader election and computation of local identifiers for programmable matter
- Shape formation by programmable particles
- Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
- Line reconfiguration by programmable particles maintaining connectivity
- Connected reconfiguration of lattice-based cellular structures by finite-memory robots
- Improved Leader Election for Self-organizing Programmable Matter
- Computing coordinated motion plans for robot swarms: the CG:SHOP challenge 2021
- Terminating distributed construction of shapes and patterns in a fair solution of automata
- Distributed transformations of Hamiltonian shapes based on line moves
- Improved Tradeoffs for Leader Election
- The canonical amoebot model: algorithms and concurrency control
- The canonical amoebot model: algorithms and concurrency control
- Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes
- Shape formation by programmable particles
- A Markov chain algorithm for compression in self-organizing particle systems
- Stationary and deterministic leader election in self-organizing particle systems
- Efficient Deterministic Leader Election for Programmable Matter
- Molecular pattern formation on grids in the \textsc{Moblot} model
- Universal coating for programmable matter
This page was built for publication: Leader election and shape formation with self-organizing programmable matter
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948412)
