Markov Chain Algorithms for Emergent Phenomena in Self-Organizing Particle Systems

Abstract

We investigate Markov chain algorithms that can accomplish global emergent phenomena in a distributed setting, namely in self-organizing particle systems, an abstraction of programmable matter. These particle systems are composed of individual computational units known as particles that each have limited memory, strictly local communication abilities, and modest computational power, and which collectively solve system-wide problems of movement and coordination. We introduce fully distributed, asynchronous, stochastic algorithms for two problems: separation and alignment, both of which we formally define. We then rigorously analyze the correctness and convergence of our distributed, stochastic algorithms by leveraging techniques from Markov chain analysis. Our theoretical results are complemented by simulations.