Improved Leader Election for Self-Organizing Programmable Matter
This provides an efficient solution to a fundamental problem in self-organizing particle systems, improving over previous algorithms that required more rounds or global knowledge.
They present a local-control algorithm for leader election in programmable matter that runs in O(n) asynchronous rounds with high probability, using only constant memory per particle and no global information.
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.