The notion of programmable matter [Toffoli and Margolus 1993] and specifically, Ameobots [Derakhshandeh, Richa, Dolev, Scheideler, Gmyr and Strothmann 2014] envisions matter as being composed of tiny weak robots called “particles”, each with no unique identity, very limited memory size and very limited abilities for movement, computation, environment sensing, and communication. At the same time, hardware researchers in various places have been developing such particles. Multiple studies have been addressing how entities that are that weak can even cooperate and what they can achieve by cooperation. See e.g. work on the coating of objects (for protection and for coloring) and forming bridges.
An important primitive used often for coordinating such tasks is the election of a unique leader.
Given leader election as a building block, it is known that various tasks in programmable matter can be performed, or improved. Interestingly, in the past, deterministic algorithms either elected multiple co-leaders in cases of symmetrical shapes of the programmable matter, or relied on various assumptions on the particles, such as initially forming a specific shape (no holes), or initially sharing a common chirality.
We show that the common definition of a scheduler for the Ameobot model, together with the movement ability of the particles, allows the development of deterministic leader election algorithms in spite of impossibility results presented in the past for other models. Let us note that previous leader election algorithms have not exploited movements. Also, previous Ameobot algorithms in general have not allowed the programmable matter to ever get disconnected (where a graph is defined with the particles as nodes and two particles are neighbors if they are “close to each other”). We show that by allowing the matter to disconnect temporarily, the time complexity of deterministic leader election algorithms becomes as low as that of known probabilistic algorithms.
This talk is based on papers with Fabien Dufoloun, Yuval Emek, Ron Lavi, and William Mosses Jr. [ICALP’19],[PODC21]