Coordinating Amoebots via Reconfigurable Circuits

We consider an extension to the geometric amoebot model that allows amoebots to form so-called circuits. Given a connected amoebot structure, a circuit is a subgraph formed by the amoebots that permits the instant transmission of signals. We show that such an extension allows for significantly faster solutions to a variety of problems related to programmable matter. More specifically, we provide algorithms for leader election, consensus, compass alignment, chirality agreement, and shape recognition. Leader election can be solved in $$ rounds, with high probability (w.h.p.), consensus in $$ rounds, and both, compass alignment and chirality agreement, can be solved in $$ rounds, w.h.p. For shape recognition, the amoebots have to decide whether the amoebot structure forms a particular shape. We show that the amoebots can detect a shape composed of triangles within $$ rounds. Finally, we show how the amoebots can detect a parallelogram with linear and polynomial side ratio within $$ rounds, w.h.p.