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

Abstract

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 \cdot 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 $\lambda$. In particular, for all $0 < \lambda < \sqrt{2}$, there is a constant $\beta < 1$ such that at stationarity, with all but an exponentially small probability, the perimeter will be at least $\beta \cdot p_{max}$, where $p_{max}$ is the maximum possible perimeter.

Publication
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
Sarah Cannon
Sarah Cannon
Assistant Professor of Mathematics
Joshua J. Daymude
Joshua J. Daymude
Assistant Professor, Computer Science

I am a Christian and assistant professor in computer science studying collective emergent behavior and programmable matter through the lens of distributed computing, stochastic processes, and bio-inspired algorithms. I also love gaming and playing music.

Dana Randall
Dana Randall
Professor of Computer Science
Andréa W. Richa
Andréa W. Richa
Professor of Computer Science

Related