Leader Election and Shape Formation with Self-Organizing Programmable Matter

Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andréa W. Richa, and Christian Scheideler.[arXiv] [Springer] — Conference paper in DNA Computing and Molecular Programming – 21st International Conference (DNA21), pp. 117-132, 2015.[ACM] — Brief announcement in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC ’15), pp. 67-69, 2015.

Overview

Leader election is a well-studied problem in distributed computing. In our setting, each particle in a connected system (under the usual constraints of the amoebot model) must cooperate to eventually elect a single, unique leader. Said more formally, there must exist some time in the future at which a particle declares itself the leader, after which no other particle may ever do the same. The challenge in solving this problem under the amoebot model is twofold:

  1. All particles are anonymous, meaning they don’t have identifiers. This means that classical approaches relying on comparing identifiers won’t work for us.
  2. Particles have strictly local sensing, meaning each particle can only see and communicate with the 1-6 neighbors adjacent to it. This means that particles have to make decisions based on very little information, and long-range coordination is nontrivial to orchestrate.

We first prove an impossibility result: without the geometric information provided by the triangular lattice, it is impossible to solve leader election with any non-negligible success probability. Moreover, this implies that it is also impossible to solve line formation (forming a shape where all particles except the endpoints have exactly two neighbors) without geometric information.

Using the geometric information from the triangular lattice, we devise an algorithm where particles compete for leadership on each boundary of the system independently. Once these competitions are over, any remaining candidates on inner boundaries of the system are demoted while the candidate on the unique outer boundary is confirmed as the leader. This algorithm is analyzed for correctness and runtime in a simplified, synchronous setting where all particles act in lock-step. Additionally, the details of how particles obtain various global knowledge (e.g., if they’re on an inner or outer boundary) are temporarily ignored. In this simplified setting, the algorithm is shown to be correct and to terminate in O(Lmax) rounds with high probability, where Lmax is the length of the longest boundary.

Details are then given for translating this algorithm to the asynchronous setting, where particles have to communicate and coordinate in order to glean information from outside their neighborhoods. However, this version of the algorithm is not analyzed.

In the simulation below, red agents and segments are competing to have the longest segment. To aid in breaking ties, the gold agents and segments flip a coin and transfer their candidacy to the next agent if the coin comes up heads. A blue agent and its segment are performing solitude verification to determine if they are the only remaining candidate on their border. Once solitude is verified, the agent turns green. The inner-outer border test is performed next. If the agent determines it is on an inner border, it deletes its border and revokes candidacy; otherwise, the agent is on the outer border and declares itself the system leader (green border).

Resources

  • [GitHub] This algorithm was implemented in AmoebotSim by Ryan Yiu, Joshua J. Daymude, and Robert Gmyr.
  • [Talk Slides] Thim Strothmann. DNA Computing and Molecular Programming – 21st International Conference (DNA21), Boston/Cambridge, MA, USA. August 19, 2015.
  • [Talk Slides] Thim Strothmann. 2015 ACM Symposium on Principles of Distributed Computing (PODC ’15), Donostia-San Sebastian, Spain. July 21, 2015.

Press

None.

BibTeX

@inproceedings{Derakhshandeh2015,
title = {Leader Election and Shape Formation with Self-Organizing Programmable Matter},
author = {Derakhshandeh, Zahra and Gmyr, Robert and Strothmann, Thim and Bazzi, Rida A. and Richa, Andr\’ea W. and Scheideler, Christian}, booktitle = {{DNA} Computing and Molecular Programming — 21st International Conference},
series = {DNA21}, pages = {117–132},
year = {2015} } @inproceedings{Derakhshandeh2015,
title = {Brief Announcement: On the Feasibility of Leader Election and Shape Formation with Self-Organizing Programmable Matter},
author = {Derakhshandeh, Zahra and Gmyr, Robert and Strothmann, Thim and Bazzi, Rida A. and Richa, Andr\’ea W. and Scheideler, Christian}, booktitle = {Proceedings of the 2015 {ACM} Symposium on Principles of Distributed Computing},
series = {PODC ’15},
pages = {67–69},
year = {2015} }

Related Publications

There were several difficulties in analyzing the distributed, asynchronous protocol for this algorithm. In an effort to obtain an algorithm with clearer analysis and better guarantees, this algorithm was supplanted by the Improved Leader Election algorithm in 2017.