2017/01/13 by Daymude, Joshua J., Gmyr, Robert, Richa, Andrea W. +2
#Distributed #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1701.03616
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.