Brief Announcement: On The Feasibility Of Leader Election And Shape Formation With Self-Organizing Programmable Matter

Imagine that we had a piece of matter that can change its physical properties like shape, density, conductivity, or color in a programmable fashion based on either user input or autonomous sensing. This is the vision behind what is commonly known as programmable matter. Many proposals have already been made for realizing programmable matter, ranging from DNA tiles, shape-changing molecules, and cells created via synthetic biology to reconfigurable modular robotics. We are particularly interested in programmable matter consisting of simple elements called particles that can compute, bond, and move, and the feasibility of solving fundamental problems relevant for programmable matter with these particles. As a model for that programmable matter, we will use a general form of the amoebot model first proposed in SPAA 2014, and as examples of fundamental problems we will focus on leader election and shape formation. For shape formation, we investigate the line formation problem, i.e. we are searching for a local-control protocol so that for any connected structure of particles, the particles will eventually form a line.Prior results on leader election imply that in the general amoebot model there are instances in which leader election cannot be solved by local-control protocols. Additionally, we can show that if there is a local-control protocol that solves the line formation problem, then there is also a protocol that solves the leader election problem, which implies that in the general amoebot model also the line formation problem cannot be solved by a local-control protocol.We also consider a geometric variant of the amoebot model by restricting the particle structures to form a connected subset on a triangular grid. For these structures we can show that there are local-control protocols for the leader election problem and the line formation problem. The protocols can also be adapted to other regular geometric structures demonstrating that it is advisable to restrict particle structures to such structures.