Algorithms for Programmable Matter in a Physiological Medium

• Applicant: Professor Dr. Christian Scheideler
• Subject Area: Theoretical Computer Science
• Term: from 2018 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 406519795

• Final Report Year: 2023

Final Report Abstract

The goal of the project was to study algorithms for programmable matter in a physiological medium. The basis of our work was the amoebot model, which was proposed by us in 2014 and has already proved to be very useful for algorithmic research on programmable matter. Besides some overdue groundwork on the amoebot model, we extended the state of the art in several directions. First of all, we proposed a new variant of our amoebot model in which the amoebots are allowed to establish circuits, and developed algorithms on top of this model that significantly improved the runtime of several fundamental problems like leader election, compass alignment, and the formation of basic shapes. We also proposed an extension to study fault-tolerance and presented a first algorithm for the formation of a basic shape that can handle an arbitrary number of temporary crash failures of amoebots. On top of that, we proposed an extension of the amoebot model, which was originally designed for the 2D case, to the 3D case, and we demonstrated the feasilibity of designing algorithms for that model by presenting a solution for coating any 3D object that does not have narrow passages.

Publications

• Computing by Programmable Particles. Lecture Notes in Computer Science, 615-681. Springer International Publishing.
  Daymude, Joshua J.; Hinnenthal, Kristian; Richa, Andréa W. & Scheideler, Christian
  
• Design of nanorobots for exposing cancer cells. Nanotechnology, 30(31), 315501.
  Dolev, Shlomi; Narayanan, Ram Prasadh & Rosenblit, Michael
  
• Forming tile shapes with simple robots. Natural Computing, 19(2), 375-390.
  Gmyr, Robert; Hinnenthal, Kristian; Kostitsyna, Irina; Kuhn, Fabian; Rudolph, Dorian; Scheideler, Christian & Strothmann, Thim
  
• Convex Hull Formation for Programmable Matter. Proceedings of the 21st International Conference on Distributed Computing and Networking, 1-10. ACM.
  Daymude, Joshua J.; Gmyr, Robert; Hinnenthal, Kristian; Kostitsyna, Irina; Scheideler, Christian & Richa, Andréa W.
  
• Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 223-233. ACM.
  Feldmann, Michael; Khazraei, Ardalan & Scheideler, Christian
  
• Towards synchronizing radio communication of In-Vivo nanorobots. Nano Futures, 4(3), 035008.
  Dolev, Shlomi; Narayanan, Ram Prasadh & Scheideler, Christian
  
• Coordinating Amoebots via Reconfigurable Circuits. Lecture Notes in Computer Science, 484-488. Springer International Publishing.
  Feldmann, Michael; Padalkin, Andreas; Scheideler, Christian & Dolev, Shlomi
  
• Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization. Proceedings of the Eight Annual ACM International Conference on Nanoscale Computing and Communication, 1-2. ACM.
  Dolev, Shlomi; Narayanan, Ram Prasadh; Scheideler, Christian & Schindelhauer, Christian
  
• The Canonical Amoebot Model: Algorithms and Concurrency Control. DISC 2021: 20:1-20:19.
  Joshua J. Daymude, Andréa W. Richa & Christian Scheideler
  
• Coordinating Amoebots via Reconfigurable Circuits. Journal of Computational Biology, 29(4), 317-343.
  Feldmann, Michael; Padalkin, Andreas; Scheideler, Christian & Dolev, Shlomi
  
• Fault-Tolerant Shape Formation in the Amoebot Model. DNA 2022: 9:1-9:22.
  Irina Kostitsyna, Christian Scheideler & Daniel Warner
  
• Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems. SAND 2022: 12:1-12:19.
  Joshua J. Daymude, Andréa W. Richa & Christian Scheideler
  
• The Structural Power of Reconfigurable Circuits in the Amoebot Model. DNA 2022: 8:1-8:22.
  Andreas Padalkin, Christian Scheideler & Daniel Warner