Document Open Access Logo

Deterministic Leader Election in Programmable Matter

Authors Yuval Emek, Shay Kutten, Ron Lavi, William K. Moses Jr.

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.140.pdf
  • Filesize: 482 kB
  • 14 pages

Document Identifiers

Author Details

Yuval Emek
  • Faculty of Industrial Engineering and Management, Technion - IIT, Haifa, Israel
Shay Kutten
  • Faculty of Industrial Engineering and Management, Technion - IIT, Haifa, Israel
Ron Lavi
  • Faculty of Industrial Engineering and Management, Technion - IIT, Haifa, Israel
William K. Moses Jr.
  • Faculty of Industrial Engineering and Management, Technion - IIT, Haifa, Israel

Funding

  • Emek, Yuval: The work of Y. Emek was supported in part by an Israeli Science Foundation grant number 1016/17.
  • Kutten, Shay: The work of this author was supported in part by a grant from the Bi-national Science Foundation.
  • Lavi, Ron: This research was supported by the ISF-NSFC joint research program (grant No. 2560/17).
  • Moses Jr., William K.: The work of this author was supported in part by a grant from the Israeli Ministry of Science.

Cite As Get BibTex

Yuval Emek, Shay Kutten, Ron Lavi, and William K. Moses Jr.. Deterministic Leader Election in Programmable Matter. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 140:1-140:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.140

Abstract

Addressing a fundamental problem in programmable matter, we present the first deterministic algorithm to elect a unique leader in a system of connected amoebots assuming only that amoebots are initially contracted. Previous algorithms either used randomization, made various assumptions (shapes with no holes, or known shared chirality), or elected several co-leaders in some cases. 
Some of the building blocks we introduce in constructing the algorithm are of interest by themselves, especially the procedure we present for reaching common chirality among the amoebots. Given the leader election and the chirality agreement building block, it is known that various tasks in programmable matter can be performed or improved.
The main idea of the new algorithm is the usage of the ability of the amoebots to move, which previous leader election algorithms have not used.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Computing methodologies → Mobile agents
  • Theory of computation → Self-organization
Keywords
  • programmable matter
  • geometric amoebot model
  • leader election

Metrics

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

Related Versions

References

  1. Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A stochastic approach to shortcut bridging in programmable matter. Natural Computing, 17(4):723-741, 2018. Google Scholar
  2. Rida A. Bazzi and Joseph L. Briones. Brief Announcement: Deterministic Leader Election in Self-organizing Particle Systems. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 381-386. Springer, 2018. Google Scholar
  3. Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A Markov chain algorithm for compression in self-organizing particle systems. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 279-288. ACM, 2016. Google Scholar
  4. Joshua J. Daymude, Zahra Derakhshandeh, Robert Gmyr, Alexandra Porter, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. On the runtime of universal coating for programmable matter. Natural Computing, 17(1):81-96, 2018. Google Scholar
  5. Joshua J. Daymude, Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Christian Scheideler, and Andréa W. Richa. Convex Hull Formation for Programmable Matter. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.06149.
  6. Joshua J. Daymude, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Improved leader election for self-organizing programmable matter. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pages 127-140. Springer, 2017. Google Scholar
  7. Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler. Computing by Programmable Particles. In Distributed Computing by Mobile Entities, pages 615-681. Springer, 2019. Google Scholar
  8. 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 Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures, pages 220-222. ACM, 2014. Google Scholar
  9. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. An algorithmic framework for shape formation problems in self-organizing particle systems. In Proceedings of the Second Annual International Conference on Nanoscale Computing and Communication, page 21. ACM, 2015. Google Scholar
  10. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Universal shape formation for programmable matter. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pages 289-299. ACM, 2016. Google Scholar
  11. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Universal coating for programmable matter. Theoretical Computer Science, 671:56-68, 2017. Google Scholar
  12. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann, and Shimrit Tzur-David. Infinite object coating in the amoebot model. arXiv preprint, 2014. URL: http://arxiv.org/abs/1411.2356.
  13. Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida Bazzi, Andréa W. Richa, and Christian Scheideler. Leader election and shape formation with self-organizing programmable matter. In International Workshop on DNA-Based Computers, pages 117-132. Springer, 2015. Google Scholar
  14. Giuseppe Antonio Di Luna, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. Line recovery by programmable particles. In 19th International Conference on Distributed Computing and Networking, ICDCN 2018, volume 133180, pages 1-10. Association for Computing Machinery, 2018. Google Scholar
  15. Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. Shape Formation by Programmable Particles. In 21st International Conference on Principles of Distributed Systems, 2017. Google Scholar
  16. Reinhard Diestel. Graph theory. 2005. Grad. Texts in Math, 101, 2005. Google Scholar
  17. Nicolas Gastineau, Wahabou Abdou, Nader Mbarek, and Olivier Togni. Distributed leader election and computation of local identifiers for programmable matter. arXiv preprint, 2018. URL: http://arxiv.org/abs/1807.10461.
  18. Adrian Segall. Distributed network protocols. IEEE transactions on Information Theory, 29(1):23-35, 1983. Google Scholar
  19. Tommaso Toffoli and Norman Margolus. Programmable matter: concepts and realization. Physica D: Nonlinear Phenomena, 47(1-2):263-272, 1991. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact