The Structural Power of Reconfigurable Circuits in the Amoebot Model

Authors Andreas Padalkin , Christian Scheideler , Daniel Warner



PDF
Thumbnail PDF

File

LIPIcs.DNA.28.8.pdf
  • Filesize: 1.4 MB
  • 22 pages

Document Identifiers

Author Details

Andreas Padalkin
  • Universität Paderborn, Germany
Christian Scheideler
  • Universität Paderborn, Germany
Daniel Warner
  • Universität Paderborn, Germany

Cite AsGet BibTex

Andreas Padalkin, Christian Scheideler, and Daniel Warner. The Structural Power of Reconfigurable Circuits in the Amoebot Model. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DNA.28.8

Abstract

The amoebot model [Derakhshandeh et al., SPAA 2014] has been proposed as a model for programmable matter consisting of tiny, robotic elements called amoebots. We consider the reconfigurable circuit extension [Feldmann et al., JCB 2022] of the geometric (variant of the) amoebot model that allows the amoebot structure to interconnect amoebots by so-called circuits. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits. We start with some fundamental problems like the stripe computation problem where, given any connected amoebot structure S, an amoebot u in S, and some axis X, all amoebots belonging to axis X through u have to be identified. Second, we consider the global maximum problem, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can then be used to solve the skeleton problem, where a (not necessarily simple) cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can then be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions will then allow the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure. The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmic-time solutions to all of these problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Computational geometry
Keywords
  • progammable matter
  • amoebot model
  • reconfigurable circuits
  • spanning tree
  • symmetry detection

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. John Calvin Alumbaugh, Joshua J. Daymude, Erik D. Demaine, Matthew J. Patitz, and Andréa W. Richa. Simulation of programmable matter systems using active tile-based self-assembly. In DNA, volume 11648 of Lecture Notes in Computer Science, pages 140-158. Springer, 2019. Google Scholar
  2. Joshua J. Daymude, Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Christian Scheideler, and Andréa W. Richa. Convex hull formation for programmable matter. In ICDCN, pages 2:1-2:10. ACM, 2020. Google Scholar
  3. Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler. Computing by programmable particles. In Distributed Computing by Mobile Entities, volume 11340 of Lecture Notes in Computer Science, pages 615-681. Springer, 2019. Google Scholar
  4. Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. The canonical amoebot model: Algorithms and concurrency control. In DISC, volume 209 of LIPIcs, pages 20:1-20:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  5. Joshua J. Daymude, Andréa W. Richa, and Jamison W. Weber. Bio-inspired energy distribution for programmable matter. In ICDCN, pages 86-95. ACM, 2021. Google Scholar
  6. Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: amoebot - a new model for programmable matter. In SPAA, pages 220-222. ACM, 2014. Google Scholar
  7. Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andréa W. Richa, and Christian Scheideler. Leader election and shape formation with self-organizing programmable matter. In DNA, volume 9211 of Lecture Notes in Computer Science, pages 117-132. Springer, 2015. Google Scholar
  8. Michael Feldmann, Andreas Padalkin, Christian Scheideler, and Shlomi Dolev. Coordinating amoebots via reconfigurable circuits. J. Comput. Biol., 29(4):317-343, 2022. Google Scholar
  9. Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. Shape formation by programmable particles. Distributed Comput., 33(1):69-101, 2020. Google Scholar
  10. Ali Mashreghi and Valerie King. Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model. Distributed Comput., 34(4):283-299, 2021. Google Scholar
  11. Jennifer E. Padilla, Ruojie Sha, Martin Kristiansen, Junghuei Chen, Natasha Jonoska, and Nadrian C. Seeman. A signal-passing dna-strand-exchange mechanism for active self-assembly of dna nanostructures. Angewandte Chemie International Edition, 54(20):5939-5942, 2015. Google Scholar
  12. Dominic Scalise and Rebecca Schulman. Controlling matter at the molecular scale with dna circuits. Annual Review of Biomedical Engineering, 21(1):469-493, 2019. PMID: 31167101. URL: https://doi.org/10.1146/annurev-bioeng-060418-052357.
  13. Shalin Shah, Jasmine Wee, Tianqi Song, Luis Ceze, Karin Strauss, Yuan-Jyue Chen, and John Reif. Using strand displacing polymerase to program chemical reaction networks. Journal of the American Chemical Society, 142(21):9587-9593, 2020. PMID: 32364723. URL: https://doi.org/10.1021/jacs.0c02240.
  14. Tianqi Song, Abeer Eshra, Shalin Shah, Hieu Bui, Daniel Fu, Ming Yang, Reem Mokhtar, and John Reif. Fast and compact dna logic circuits based on single-stranded gates using strand-displacing polymerase. Nature Nanotechnology, 14(11):1075-1081, November 2019. URL: https://doi.org/10.1038/s41565-019-0544-5.
  15. Tommaso Toffoli and Norman Margolus. Programmable matter: Concepts and realization. Int. J. High Speed Comput., 5(2):155-170, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail