Abstract
We consider an extension to the geometric amoebot model that allows amoebots to form so-called circuits. Given a connected amoebot structure, a circuit is a subgraph formed by the amoebots that permits the instant transmission of signals. We show that such an extension allows for significantly faster solutions to a variety of problems related to programmable matter. More specifically, we provide algorithms for leader election, consensus, compass alignment, chirality agreement, and shape recognition. Leader election can be solved in \(\varTheta (\log n)\) rounds, w.h.p., consensus in O(1) rounds, and both, compass alignment and chirality agreement, can be solved in \(O(\log n)\) rounds, w.h.p. For shape recognition, the amoebots have to decide whether the amoebot structure forms a particular shape. We show that the amoebots can detect a shape composed of triangles within O(1) rounds. Finally, we show how the amoebots can detect a parallelogram with linear and polynomial side ratio within \(\varTheta (\log {n})\) rounds, w.h.p.
This work has been supported by the DFG Project SCHE 1592/6-1 (PROGMATTER). A full version of this brief announcement is available online at the following address: https://arxiv.org/abs/2105.05071.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
An event holds with high probability (w.h.p.) if it holds with probability at least \(1 - 1/n^c\) where the constant c can be made arbitrarily large.
References
Daymude, J.J., Richa, A.W., Scheideler, C.: The canonical amoebot model: algorithms and concurrency control. In: Gilbert, S. (ed.) 35th International Symposium on Distributed Computing (DISC 2021), LIPIcs, vol. 209, pp. 20:1–20:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany (2021). https://doi.org/10.4230/LIPIcs.DISC.2021.20. https://drops.dagstuhl.de/opus/volltexte/2021/14822
Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Brief announcement: amoebot - a new model for programmable matter. In: SPAA, pp. 220–222. ACM (2014)
Dufoulon, F., Kutten, S., Moses Jr., W.K.: Efficient deterministic leader election for programmable matter. In: PODC, pp. 103–113. ACM (2021)
Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C.: Shape recognition by a finite automaton robot. In: MFCS. LIPIcs, vol. 117, pp. 52:1–52:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G., Yamauchi, Y.: Shape formation by programmable particles. Distrib. Comput. 33(1), 69–101 (2019). https://doi.org/10.1007/s00446-019-00350-6
Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: STOC, pp. 459–468. ACM (2000)
Toffoli, T., Margolus, N.: Programmable matter: concepts and realization. Int. J. High Speed Comput. 5(2), 155–170 (1993)
Woods, D., Chen, H., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: ITCS, pp. 353–354. ACM (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Feldmann, M., Padalkin, A., Scheideler, C., Dolev, S. (2021). Coordinating Amoebots via Reconfigurable Circuits. In: Johnen, C., Schiller, E.M., Schmid, S. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2021. Lecture Notes in Computer Science(), vol 13046. Springer, Cham. https://doi.org/10.1007/978-3-030-91081-5_34
Download citation
DOI: https://doi.org/10.1007/978-3-030-91081-5_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-91080-8
Online ISBN: 978-3-030-91081-5
eBook Packages: Computer ScienceComputer Science (R0)