One major difficulty in selforganizing multiagent systems research is the lack of theoretical models that allow us to ask fundamental questions about computability and complexity. Given a global goal and a multiagent system where the agents have limited capability (finite state, limited view), we can ask many theoretical questions: Is the global task solvable? What are the minimal agent capabilities required to robustly solve the task? What are the lower bounds on parallelism and scalability? Answers to these theoretical questions have important practical implications: they tell us fundamental limits on what globaltolocal algorithms and compilers can achieve, and how agent design restricts the set of tasks that the system is able to solve.
We have developed the beginnings of a globaltolocal theory that can answer such questions, in the context of selforganizing pattern formation tasks on 1D asynchronous cellular automata. This work was developed by Daniel Yamins (now faculty at Stanford) during his PhD. It is inspired in part by the amazingly robust and complex pattern formation that is achieved by biological systems such as the fruit fly embryo, as well as the engineering application of pattern formation ideas to robot swarms, modular robots and selfassembly.
Some of the contributions of this work are:

Yamins showed that there is a necessary and sufficient condition, Local Checkability, that not only allows us to answer the question of existence, but also produce minimal state agent programs for selfrepairing pattern formation. Local checkability can be thought of as a distributed voting (or stopping) condition and can be used to solve three problems.
 An existence problem: Local checkability forms a simple criterion that any robustly solvable goal must satisfy. If a pattern is not locally checkable, no robust local rule can selforganize it. The minimum radius for local checkability gives us a way to reason about minimal agent programs. We have used local checkability to show lower bounds on agent state and communication for several common classes of patterns (repeated, scaleinvariant).
 A construction problem: For all patterns that are locally checkable, we can use the local check to algorithmically derive local rule that generates it robustly. The local agent rule is by construction scaleinvariant (works for varying numbers of agents), robust (works for any initial condition and asynchronous timing), and self repairing (pattern reemerges after perturbation).
 A resource problem: The two main resource parameters of the model, the agent interaction radius and agent memory size, exist in a radiusstate resource tradeoff. We describe algorithms for tuning along the continuum between largeradius/lowstate and lowradius /highstate implementations.
 By combining these three techniques, we are able to build a GlobaltoLocal Compiler that implements this theory: the compiler takes as an input a logicbased description of a pattern or a set of example patterns, derives a local checkability condition, and produces a cellular automata rule that is both scalable and selfrepairing.
This work has led to many new insights into current globaltolocal compilers, for example how eﬃcient they are in terms of agent state and time. It has also revealed new and surprising connections between cellular automata and traditional computing models (such as Turing machines, Languages, and DeBruin graphs). An important future area will be generalizing this work from cellular automata to other multiagent settings, and using this model to better understand existing selforganizing systems. Ultimately, this type of theory will provide an important design tool for selforganizing systems, by allowing us to reason about the complexity and scalability of embedded multiagent systems where agents have limited capability.