POSTPONED: new date tba Synthesis of local-rule processes: success stories and challenges

Abstract

POSTPONED: NEW DATE TBA How does one systematically program global computations in systems of a vast number of components restricted to local-rule interaction in a flat hierarchy? This question has been around since the '50s when cellular automata were introduced as models of such systems. The question posed here is known as the synthesis problem, and remains poorly understood. Terms like self-assembling and self-organizing are often used to describe computations on such systems. We mention a number of instances of local-rule processes at widely different scales in computer and network engineering: molecular computation, sensor-network computation, and computation on the Web. Typical performance questions that we address include the convergence to useful, non-degenerate behavior: does it always occur, and if so, how long does it take?