A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

We consider programmable matter as a collection of simple computational elements (or particles) with limited (constant size) memory that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. More specifically, we seek fully distributed, local, and asynchronous algorithms that lead the system to converge to a configuration with small perimeter. We present a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration with no holes. The algorithm takes as input a bias parameter lambda, where lambda > 1 corresponds to particles favoring inducing more lattice triangles within the particle system. We show that for all lambda > 5, there is a constant alpha > 1 such that at stationarity with all but exponentially small probability the particles are alpha-compressed, meaning the perimeter of the system configuration is at most alpha . p(min), where p(min) is the minimum possible perimeter of the particle system. We additionally prove that the same algorithm can be used for expansion for small values of A lambda in particular, for all 0 < lambda < root 2 there is a constant beta < 1 such that at stationarity, with all but an ex ponentially small probability, the perimeter will be at least beta . p(max) where p(max) is the maximum possible perimeter.