Computation in Ad-hoc Networks of Very Limited Agents

Abstract

We explore the power of very limited agents to organize useful computation in ad-hoc networks of arbitrary size. The models we consider are intended to be fundamental and applicable to diverse areas, such as sensor networks, populations of agents engaged in social or economic behavior, and interactions in chemical and biological networks.

For example, we show that a soup of finite automata can compute semilinear predicates of their initial states, while automata in an unknown degree-bounded communication graph are computationally much more powerful. I will describe results from joint work with James Aspnes, Michael Fischer, Rene Peralta, Eric Ruppert, Melody Chan, Zoe Diamadi, David Eisenstat, and Hong Jiang.