Programmable matter explores how collections of computationally limited agents acting locally and asynchronously can achieve some useful coordinated behavior.  We take a stochastic approach using techniques from randomized algorithms and statistical physics to develop distributed algorithms for emergent collective behaviors that give guarantees and are robust to failures.