TY - GEN
T1 - Improved leader election for self-organizing programmable matter
AU - Daymude, Joshua J.
AU - Gmyr, Robert
AU - Richa, Andrea
AU - Scheideler, Christian
AU - Strothmann, Thim
N1 - Funding Information:
J. J. Daymude and A. W. Richa—Supported in part by NSF awards CCF-1422603 and CCF-1637393. R. Gmyr, C. Scheideler and T. Strothmann—Supported in part by DFG grant SCHE 1592/3-1.
Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - We consider programmable matter that consists of computationally limited devices (called particles) that are able to self-organize in order to achieve some collective goal without the need for central control or external intervention. We use the geometric amoebot model to describe such self-organizing particle systems, which defines how particles can actively move and communicate with one another. In this paper, we present an efficient local-control algorithm which solves the leader election problem in O(n) asynchronous rounds with high probability, where n is the number of particles in the system. Our algorithm relies only on local information — particles do not have unique identifiers, any knowledge of n, or any sort of global coordinate system — and requires only constant memory per particle.
AB - We consider programmable matter that consists of computationally limited devices (called particles) that are able to self-organize in order to achieve some collective goal without the need for central control or external intervention. We use the geometric amoebot model to describe such self-organizing particle systems, which defines how particles can actively move and communicate with one another. In this paper, we present an efficient local-control algorithm which solves the leader election problem in O(n) asynchronous rounds with high probability, where n is the number of particles in the system. Our algorithm relies only on local information — particles do not have unique identifiers, any knowledge of n, or any sort of global coordinate system — and requires only constant memory per particle.
UR - http://www.scopus.com/inward/record.url?scp=85040123122&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85040123122&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-72751-6_10
DO - 10.1007/978-3-319-72751-6_10
M3 - Conference contribution
AN - SCOPUS:85040123122
SN - 9783319727509
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 127
EP - 140
BT - Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers
A2 - Mosteiro, Miguel A.
A2 - Jurdzinski, Tomasz
A2 - Fernandez Anta, Antonio
A2 - Zhang, Yanyong
PB - Springer Verlag
T2 - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017
Y2 - 4 September 2017 through 8 September 2017
ER -