Description:

Title: Local-global principles for programming collectives

Abstract:  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.  By analyzing the Gibbs distribution of various fixed-magnetization models from equilibrium statistical mechanics, we show that particles moving stochastically according to local affinities can solve various useful collective tasks. Finally, we will briefly introduce new tools that may prove fruitful in nonequilibrium settings as well.