research-article

Efficient Deterministic Leader Election for Programmable Matter

Authors:

Fabien Dufoulon,

William K. Moses Jr.Authors Info & Claims

PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

Pages 103 - 113

https://doi.org/10.1145/3465084.3467900

Published: 23 July 2021 Publication History

Abstract

It 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 that allowing the system to disconnect carried a significant advantage in terms of time complexity. We demonstrate for a fundamental task, that of leader election, an algorithm where the system disconnects and then reconnects automatically in a non-trivial way (particles can move far away from their former neighbors and later reconnect to others). Moreover, the runtime of the temporarily disconnecting deterministic leader election algorithm is linear in the diameter. Hence, the disconnecting -- reconnecting algorithm is as fast as previous randomized algorithms. When comparing to previous deterministic algorithms, we note that some of the previous work assumed weaker schedulers. Still, the runtime of all the previous deterministic algorithms that did not assume special shapes of the particle system (shapes with no holes) was at least quadratic in n, where n is the number of particles in the system. (Moreover, the new algorithm is even faster in some parameters than the deterministic algorithms that did assume special initial shapes.)

Since leader election is an important module in algorithms for various other tasks, the presented algorithm can be useful for speeding up other algorithms under the assumption of a strong scheduler. This leaves open the question: "can a deterministic algorithm be as fast as the randomized ones also under weaker schedulers?''

Supplementary Material

MP4 File (PODC21-016.mp4)

It 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 that allowing the system to disconnect carried a significant advantage in terms of time complexity. We demonstrate for a fundamental task, that of leader election, an algorithm where the system disconnects and then reconnects automatically in a non-trivial way (particles can move far away from their former neighbors and later reconnect to others). Moreover, the runtime of the temporarily disconnecting deterministic leader election algorithm is linear in the diameter. Hence, the disconnecting -- reconnecting algorithm is as fast as previous randomized algorithms.

Download
293.17 MB

References

[1]

Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. 2018. A stochastic approach to shortcut bridging in programmable matter. Natural Computing, Vol. 17, 4 (2018), 723--741.

Digital Library

[2]

Hans-Jurgen Bandelt and Victor Chepoi. 2008. Metric graph theory and geometry: a survey. Contemp. Math., Vol. 453 (2008), 49--86.

[3]

Rida A. Bazzi and Joseph L. Briones. 2019. Stationary and Deterministic Leader Election in Self-organizing Particle Systems. In Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems. Springer, 22--37.

[4]

Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. 2019. A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[5]

Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. 2016. A Markov chain algorithm for compression in self-organizing particle systems. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. ACM, 279--288.

[6]

Victor Chepoi, Feodor Dragan, and Yann Vaxès. 2002. Center and Diameter Problems in Plane Triangulations and Quadrangulations. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 346--355.

Digital Library

[7]

Joshua J. Daymude, Zahra Derakhshandeh, Robert Gmyr, Alexandra Porter, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. 2018. On the runtime of universal coating for programmable matter. Natural Computing, Vol. 17, 1 (2018), 81--96.

Digital Library

[8]

Joshua J. Daymude, Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Christian Scheideler, and André a W. Richa. 2020. Convex Hull Formation for Programmable Matter. In Proceedings of the 21st International Conference on Distributed Computing and Networking. 2:1--2:10.

Digital Library

[9]

Joshua J. Daymude, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. 2017a. Improved leader election for self-organizing programmable matter. In Proceedings of the 13th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics. Springer, 127--140.

[10]

Joshua J Daymude, Robert Gmyr, Andrea W Richa, Christian Scheideler, and Thim Strothmann. 2017b. Improved Leader Election for Self-Organizing Programmable Matter. arXiv preprint arXiv:1701.03616 (2017).

[11]

Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler. 2019. Computing by Programmable Particles. In Distributed Computing by Mobile Entities. Springer, 615--681.

[12]

Joshua J. Daymude, Andréa W. Richa, and Jamison W. Weber. 2021. Bio-Inspired Energy Distribution for Programmable Matter. In International Conference on Distributed Computing and Networking 2021. 86--95.

[13]

Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. 2014a. Brief announcement: amoebot--a new model for programmable matter. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, 220--222.

Digital Library

[14]

Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. 2015a. 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. ACM, 21:1--21:2.

Digital Library

[15]

Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. 2016. Universal shape formation for programmable matter. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, 289--299.

Digital Library

[16]

Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. 2017. Universal coating for programmable matter. Theoretical Computer Science, Vol. 671 (2017), 56--68.

[17]

Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann, and Shimrit Tzur-David. 2014b. Infinite object coating in the amoebot model. arXiv preprint arXiv:1411.2356 (2014).

[18]

Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida Bazzi, Andréa W. Richa, and Christian Scheideler. 2015b. Leader election and shape formation with self-organizing programmable matter. In Proceedings of the 21st International Conference on DNA Computing and Molecular Programming. Springer, 117--132.

Digital Library

[19]

Giuseppe Antonio Di Luna, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. 2018. Line recovery by programmable particles. In Proceedings of the 19th International Conference on Distributed Computing and Networking. Association for Computing Machinery, 4:1--4:10.

[20]

Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. 2020 a. Mobile RAM and shape formation by programmable particles. In European Conference on Parallel Processing. Springer, 343--358.

Digital Library

[21]

Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. 2020 b. Shape formation by programmable particles. Distributed Computing, Vol. 33, 1 (2020), 69--101.

Digital Library

[22]

Fabien Dufoulon, Shay Kutten, and William K. Moses Jr. 2021. Efficient Deterministic Leader Election for Programmable Matter. arXiv preprint arXiv:2106.01108 (2021).

[23]

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, Vol. 8 (2020), 207619--207634 (preliminary version appears in AAMAS 2020).

[24]

Yuval Emek, Shay Kutten, Ron Lavi, and William K. Moses Jr. 2019. Deterministic Leader Election in Programmable Matter. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming. 140:1--140:14.

[25]

Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. 2019. Distributed Computing by Mobile Entities. Current Research in Moving and Computing, Vol. 11340 (2019).

[26]

Nicolas Gastineau, Wahabou Abdou, Nader Mbarek, and Olivier Togni. 2019. Distributed Leader Election and Computation of Local Identifiers for Programmable Matter. In Proceedings of the 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018. Springer, 159--179.

[27]

Nicolas Gastineau, Wahabou Abdou, Nader Mbarek, and Olivier Togni. 2020. Leader election and local identifiers for three-dimensional programmable matter. Concurrency and Computation: Practice and Experience (2020).

[28]

Alexandra Porter and Andrea Richa. 2018. Collaborative computation in self-organizing particle systems. In Proceedings of the 17th International Conference on Unconventional Computation and Natural Computation. Springer, 188--203.

[29]

Tommaso Toffoli and Norman Margolus. 1991. Programmable matter: concepts and realization. Physica D: Nonlinear Phenomena, Vol. 47, 1--2 (1991), 263--272.

Digital Library

Cited By

Daymude JRicha AScheideler C(2023)The canonical amoebot model: algorithms and concurrency controlDistributed Computing10.1007/s00446-023-00443-336:2(159-192)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1007/s00446-023-00443-3
Navarra APrencipe GBonini STracolli M(2023)Scattering with Programmable MatterAdvanced Information Networking and Applications10.1007/978-3-031-29056-5_22(236-247)Online publication date: 20-Mar-2023
https://doi.org/10.1007/978-3-031-29056-5_22
Feldmann MPadalkin AScheideler CDolev S(2022)Coordinating Amoebots via Reconfigurable CircuitsJournal of Computational Biology10.1089/cmb.2021.036329:4(317-343)Online publication date: 1-Apr-2022
https://doi.org/10.1089/cmb.2021.0363

Index Terms

Efficient Deterministic Leader Election for Programmable Matter
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Mobile agents
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms
      1. Self-organization

Recommendations

Sublinear bounds for randomized leader election

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O ( 1 ) rounds and (with high probability) uses only O ( n log 3 / 2 n ) ...
Invited Paper: Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter
ICDCN '23: Proceedings of the 24th International Conference on Distributed Computing and Networking

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 ...
Deterministic Leader Election for Stationary Programmable Matter with Common Direction
Structural Information and Communication Complexity
Abstract
Leader 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

cover image ACM Conferences

PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

July 2021

590 pages

ISBN:9781450385480

DOI:10.1145/3465084

General Chair:
Avery Miller
University of Manitoba, Canada
,
Program Chair:
Keren Censor-Hillel
Technion, Israel

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Binational Science Foundation
Lady Davis Fellowship Trust, Technion

Conference

PODC '21

Sponsor:

PODC '21: ACM Symposium on Principles of Distributed Computing

July 26 - 30, 2021

Virtual Event, Italy

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
167
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Daymude JRicha AScheideler C(2023)The canonical amoebot model: algorithms and concurrency controlDistributed Computing10.1007/s00446-023-00443-336:2(159-192)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1007/s00446-023-00443-3
Navarra APrencipe GBonini STracolli M(2023)Scattering with Programmable MatterAdvanced Information Networking and Applications10.1007/978-3-031-29056-5_22(236-247)Online publication date: 20-Mar-2023
https://doi.org/10.1007/978-3-031-29056-5_22
Feldmann MPadalkin AScheideler CDolev S(2022)Coordinating Amoebots via Reconfigurable CircuitsJournal of Computational Biology10.1089/cmb.2021.036329:4(317-343)Online publication date: 1-Apr-2022
https://doi.org/10.1089/cmb.2021.0363

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten