Georgia Institute of Technology College of Sciences

I will present work on a new application of Markov chains to distributed computing. Motivated by programmable matter and the behavior of biological distributed systems such as ant colonies, the geometric amoebot model abstracts these processes as self-organizing particle systems where particles with limited computational power move on the triangular lattice. Previous algorithms developed in this setting have relied heavily on leader election, tree structures that are not robust to failures, and persistent memory. We developed a distributed algorithm for the compression problem, where all particles want to gather together as tightly as possible, that is based on a Markov chain and is simple, robust, and oblivious. Tools from Markov chain analysis enable rigorous proofs about its behavior, and we show compression will occur with high probability. This joint work with Joshua J. Daymude, Dana Randall, and Andrea Richa appeared at PODC 2016. I will also present some more recent extensions of this approach to other problems, which is joint work with Marta Andres Arroyo as well.