Improved Leader Election for Self-Organizing Programmable Matter

Joshua J. Daymude, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann.
[arXiv] [Springer] — Conference paper in Algorithms for Sensor Systems (ALGOSENSORS ’17), pp. 127-140, 2017.

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.

This paper improves on the algorithm given in the original Leader Election paper (2015) in several ways:

• This algorithm is entirely defined within the constraints of the amoebot model. All information is local, and the particles’ actions are asynchronous.
• This algorithm’s analysis examines the fully local, asynchronous setting (instead of the simplified synchronous setting) and is able to obtain strong with high probability guarantees.
• The algorithm is conceptually simpler to understand and implement.

This improved algorithm works in six phases:

1. Boundary setup. The particles first organize into cycles on the system’s boundaries, as in the original algorithm.
2. Segment setup. Each particle then flips a fair coin: heads means that particle is a candidate for leadership, and tails means it is immediately demoted. Each candidate claims the run of non-candidates behind it as its segment for use in the competition for leadership.
3. Identifier setup. Each candidate then generates an identifier for its segment by signalling to each of its non-candidates that they should generate a random bit. The sequence of these bits forms the segment’s identifier.
4. Identifier comparison. Using a carefully coordinated scheme, segments then compare identifiers. Candidates with larger identifiers continue to compete, while candidates with smaller identifiers are demoted. In some cases, two identifiers will be equal, triggering the next phase.
5. Solitude verification. It is possible that two identifiers are equal because there is only one candidate remaining on the boundary. To test for this, a careful scheme that uses geometric information from the lattice checks if the start and end of the candidate’s segment are the same (meaning it is the only candidate left). If this is the case, the candidate proceeds to the final phase, otherwise, it continues with identifier comparison.
6. Boundary identification. Again using geometric information (in particular, the angles along the boundary), the candidate checks whether it is on an inner boundary or the unique outer boundary. As in the original algorithm, it becomes the unique leader only if it is on the outer boundary; otherwise, it demotes itself.