Silent Programmable Matter: Coating

By Programmable Matter (PM) is usually meant a system of weak and self-organizing computational entities, called particles, which can be programmed via distributed algorithms to collectively achieve some global tasks. We consider the SILBOT model where particles are modeled as finite state automata, living and operating in the cells of a hexagonal grid. Particles are all identical, executing the same deterministic algorithm which is based on local observation of the surroundings, up to two hops. Particles are asynchronous, without any direct means of communication and disoriented but sharing a common handedness, i.e., chirality is assumed. Within such a basic model, we consider a foundational primitive for PM, that is Coating: a set of n particles must move so as to ensure the closed surrounding of an object occupying some connected cells of the grid. We present an optimal deterministic distributed algorithm – along with the correctness proof, that in Θ(n2) rounds solves the Coating problem, where a round concerns the minimal time window within which each particle is activated at least once.