TY - GEN
T1 - Stationary and Deterministic Leader Election in Self-organizing Particle Systems
AU - Bazzi, Rida A.
AU - Briones, Joseph L.
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - We propose the first stationary and deterministic protocol for the leader election problem for non-simply connected particle systems in the geometric Amoebot model in which particles have no unique identifiers but have common chirality. The solution does not require particle movement to break symmetry (stationary) and does not allow particles to make probabilistic choices (deterministic). We show that leader election is possible if and only if the proposed protocol succeeds in electing a unique leader. We show that if the protocol fails to elect a leader, it will always succeed in finding a finite set of (Formula presented) leader candidates and the system must have k-symmetry that prevents the selection of less than k candidates. The protocols runs in (Formula presented) steps, where n is the number of particles in the system. Other solutions to the leader election problem in the Amoebot model are either probabilistic, assume that the system is simply connected, and/or require stronger primitives to break symmetry.
AB - We propose the first stationary and deterministic protocol for the leader election problem for non-simply connected particle systems in the geometric Amoebot model in which particles have no unique identifiers but have common chirality. The solution does not require particle movement to break symmetry (stationary) and does not allow particles to make probabilistic choices (deterministic). We show that leader election is possible if and only if the proposed protocol succeeds in electing a unique leader. We show that if the protocol fails to elect a leader, it will always succeed in finding a finite set of (Formula presented) leader candidates and the system must have k-symmetry that prevents the selection of less than k candidates. The protocols runs in (Formula presented) steps, where n is the number of particles in the system. Other solutions to the leader election problem in the Amoebot model are either probabilistic, assume that the system is simply connected, and/or require stronger primitives to break symmetry.
UR - http://www.scopus.com/inward/record.url?scp=85076714391&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076714391&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-34992-9_3
DO - 10.1007/978-3-030-34992-9_3
M3 - Conference contribution
AN - SCOPUS:85076714391
SN - 9783030349912
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 22
EP - 37
BT - Stabilization, Safety, and Security of Distributed Systems - 21st International Symposium, SSS 2019,Proceedings
A2 - Ghaffari, Mohsen
A2 - Nesterenko, Mikhail
A2 - Tixeuil, Sébastien
A2 - Tucci, Sara
A2 - Yamauchi, Yukiko
PB - Springer
T2 - 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2019
Y2 - 22 October 2019 through 25 October 2019
ER -