Invited Paper: Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter
Pages 38 - 47
Abstract
Over three decades of scientific endeavors to realize programmable matter, a substance that can change its physical properties based on user input or responses to its environment, there have been many advances in both the engineering of modular robotic systems and the corresponding algorithmic theory of collective behavior. However, while the design of modular robots routinely addresses the challenges of realistic three-dimensional (3D) space, algorithmic theory remains largely focused on 2D abstractions such as planes and planar graphs. In this work, we formalize the 3D geometric space variant for the canonical amoebot model of programmable matter, using the face-centered cubic (FCC) lattice to represent space and define local spatial orientations. We then give a distributed algorithm for leader election in connected, contractible 2D or 3D geometric amoebot systems that deterministically elects exactly one leader in rounds under an unfair sequential adversary, where n is the number of amoebots in the system. We then demonstrate how this algorithm can be transformed using the concurrency control framework for amoebot algorithms (DISC 2021) to obtain the first known amoebot algorithm, both in 2D and 3D space, to solve leader election under an unfair asynchronous adversary.
References
[1]
Rida A. Bazzi and Joseph L. Briones. 2019. Stationary and Deterministic Leader Election in Self-Organizing Particle Systems. In Stabilization, Safety, and Security of Distributed Systems(Lecture Notes in Computer Science, Vol. 11914). 22–37. https://doi.org/10.1007/978-3-030-34992-9_3
[2]
Gregory S. Chirikjian. 1994. Kinematics of a Metamorphic Robotic System. In Proceedings of the 1994 IEEE International Conference on Robotics and Automation. 449–455. https://doi.org/10.1109/ROBOT.1994.351256
[3]
Keenan Crane, Fernando de Goes, Mathieu Desbrun, and Peter Schröder. 2013. Digital Geometry Processing with Discrete Exterior Calculus. In ACM SIGGRAPH 2013 Courses (SIGGRAPH ’13). 7:1–7:126. https://doi.org/10.1145/2504435.2504442
[4]
Gianlorenzo D’Angelo, Mattia D’Emidio, Shantanu Das, Alfredo Navarra, and Giuseppe Prencipe. 2020. Asynchronous Silent Programmable Matter Achieves Leader Election and Compaction. IEEE Access 8(2020), 207619–207634. https://doi.org/10.1109/ACCESS.2020.3038174
[5]
Joshua J. Daymude. 2021. Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter. Ph. D. Dissertation. Arizona State University, Tempe, AZ. http://login.ezproxy1.lib.asu.edu/login?url=https://www.proquest.com/dissertations-theses/collaborating-motion-distributed-stochastic/docview/2531565717/se-2?accountid=4485.
[6]
Joshua J. Daymude, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. 2017. Improved Leader Election for Self-Organizing Programmable Matter. In Algorithms for Sensor Systems(Lecture Notes in Computer Science, Vol. 10718). 127–140. https://doi.org/10.1007/978-3-319-72751-6_10
[7]
Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler. 2019. Computing by Programmable Particles. In Distributed Computing by Mobile Entities. Lecture Notes in Computer Science, Vol. 11340. Springer, Cham, 615–681. https://doi.org/10.1007/978-3-030-11072-7_22
[8]
Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. 2021. The Canonical Amoebot Model: Algorithms and Concurrency Control. In 35th International Symposium on Distributed Computing (DISC 2021)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209). 20:1–20:19. https://doi.org/10.4230/LIPIcs.DISC.2021.20
[9]
Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. 2014. Amoebot - a New Model for Programmable Matter. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures. 220–222. https://doi.org/10.1145/2612669.2612712
[10]
Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida Bazzi, Andréa W. Richa, and Christian Scheideler. 2015. Leader Election and Shape Formation with Self-Organizing Programmable Matter. In DNA Computing and Molecular Programming(Lecture Notes in Computer Science, Vol. 9211). 117–132. https://doi.org/10.1007/978-3-319-21999-8_8
[11]
Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. 2020. Shape Formation by Programmable Particles. Distributed Computing 33, 1 (2020), 69–101. https://doi.org/10.1007/s00446-019-00350-6
[12]
Fabien Dufoulon, Shay Kutten, and William K. Moses Jr.2021. Efficient Deterministic Leader Election for Programmable Matter. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 103–113. https://doi.org/10.1145/3465084.3467900
[13]
Yuval Emek, Shay Kutten, Ron Lavi, and William K. Moses Jr.2019. Deterministic Leader Election in Programmable Matter. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)(Leibniz International Proceedings in Informatics (LIPIcs)). 140:1–140:14. https://doi.org/10.4230/LIPICS.ICALP.2019.140
[14]
Robert Fitch and Zack Butler. 2008. Million Module March: Scalable Locomotion for Large Self-Reconfiguring Robots. The International Journal of Robotics Research 27, 3-4(2008), 331–343. https://doi.org/10.1177/0278364907085097
[15]
Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro (Eds.). 2019. Distributed Computing by Mobile Entities: Current Research in Moving and Computing. Lecture Notes in Computer Science, Vol. 11340. Springer, Cham. https://doi.org/10.1007/978-3-030-11072-7
[16]
Nicolas Gastineau, Wahabou Abdou, Nader Mbarek, and Olivier Togni. 2019. Distributed Leader Election and Computation of Local Identifiers for Programmable Matter. In Algorithms for Sensor Systems(Lecture Notes in Computer Science, Vol. 11410). 159–179. https://doi.org/10.1007/978-3-030-14094-6_11
[17]
Nicolas Gastineau, Wahabou Abdou, Nader Mbarek, and Olivier Togni. 2022. Leader Election and Local Identifiers for Three-dimensional Programmable Matter. Concurrency and Computation: Practice and Experience 34, 7(2022), e6067. https://doi.org/10.1002/cpe.6067
[18]
Guanqi Liang, Haobo Luo, Ming Li, Huihuan Qian, and Tin Lun Lam. 2020. FreeBOT: A Freeform Modular Self-Reconfigurable Robot with Arbitrary Connection Point - Design and Implementation. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 6506–6513. https://doi.org/10.1109/IROS45743.2020.9341129
[19]
Haobo Luo and Tin Lun Lam. 2022. Adaptive Flow Planning of Modular Spherical Robot Considering Static Gravity Stability. IEEE Robotics and Automation Letters 7, 2 (2022), 4228–4235. https://doi.org/10.1109/LRA.2022.3150028
[20]
Haobo Luo, Ming Li, Guangqi Liang, Huihuan Qian, and Tin Lun Lam. 2020. An Obstacle-Crossing Strategy Based on the Fast Self-Reconfiguration for Modular Sphere Robots. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 3296–3303. https://doi.org/10.1109/IROS45743.2020.9341162
[21]
Othon Michail and Paul G. Spirakis. 2016. Simple and Efficient Local Codes for Distributed Stable Network Construction. Distributed Computing 29, 3 (2016), 207–237. https://doi.org/10.1007/s00446-015-0257-4
[22]
Matthew J. Patitz. 2014. An Introduction to Tile-Based Self-Assembly and a Survey of Recent Results. Natural Computing 13, 2 (2014), 195–224. https://doi.org/10.1007/s11047-013-9379-4
[23]
Benoit Piranda and Julien Bourgeois. 2018. Designing a Quasi-Spherical Module for a Huge Modular Robot to Create Programmable Matter. Autonomous Robots 42(2018), 1619–1633. https://doi.org/10.1007/s10514-018-9710-0
[24]
John W. Romanishin, Kyle Gilpin, Sebastian Claici, and Daniela Rus. 2015. 3D M-Blocks: Self-Reconfiguring Robots Capable of Locomotion via Pivoting in Three Dimensions. In 2015 IEEE International Conference on Robotics and Automation (ICRA). 1925–1932. https://doi.org/10.1109/ICRA.2015.7139450
[25]
Petras Swissler and Michael Rubenstein. 2020. FireAnt3D: A 3D Self-Climbing Robot towards Non-Latticed Robotic Self-Assembly. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 3340–3347. https://doi.org/10.1109/IROS45743.2020.9341116
[26]
Pierre Thalamy, Benoît Piranda, and Julien Bourgeois. 2021. Engineering Efficient and Massively Parallel 3D Self-Reconfiguration Using Sandboxing, Scaffolding and Coating. Robotics and Autonomous Systems 146 (2021), 103875. https://doi.org/10.1016/j.robot.2021.103875
[27]
Tommaso Toffoli and Norman Margolus. 1991. Programmable Matter: Concepts and Realization. Physica D: Nonlinear Phenomena 47, 1-2 (1991), 263–272. https://doi.org/10.1016/0167-2789(91)90296-L
[28]
Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, and Peng Yin. 2013. Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science. 353–354. https://doi.org/10.1145/2422436.2422476
[29]
Ryonosuke Yamada and Yukiko Yamauchi. 2022. Search by a Metamorphic Robotic System in a Finite 3D Cubic Grid. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 221). 20:1–20:16. https://doi.org/10.4230/LIPIcs.SAND.2022.20
[30]
Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, and Masafumi Yamashita. 2017. Plane Formation by Synchronous Mobile Robots in the Three-Dimensional Euclidean Space. J. ACM 64, 3 (2017), 1–43. https://doi.org/10.1145/3060272
[31]
Mark Yim, Ying Zhang, John Lamping, and Eric Mao. 2001. Distributed Control for 3D Metamorphosis. Autonomous Robots 10, 1 (2001), 41–56. https://doi.org/10.1023/A:1026544419097
Index Terms
- Invited Paper: Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter
Recommendations
Efficient Deterministic Leader Election for Programmable Matter
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed ComputingIt was suggested that a programmable matter system (composed of multiple computationally weak mobile particles) should remain connected at all times since otherwise, reconnection is difficult and may be impossible. At the same time, it was not clear ...
Amoebot - a new model for programmable matter
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architecturesThe term programmable matter refers to matter which has the ability to change its physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion, based upon user input or autonomous sensing. This has many ...
Deterministic Leader Election for Stationary Programmable Matter with Common Direction
Structural Information and Communication ComplexityAbstractLeader Election is an important primitive for programmable matter, since it is often an intermediate step for the solution of more complex problems. Although the leader election problem itself is well studied even in the specific context of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2023
461 pages
ISBN:9781450397964
DOI:10.1145/3571306
Copyright © 2023 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 January 2023
Check for updates
Author Tags
Qualifiers
- Invited-talk
- Research
- Refereed limited
Funding Sources
- NSF
- ARO
- MF
- ASUBDI
Conference
ICDCN 2023
ICDCN 2023: 24th International Conference on Distributed Computing and Networking
January 4 - 7, 2023
Kharagpur, India
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 145Total Downloads
- Downloads (Last 12 months)95
- Downloads (Last 6 weeks)16
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in