Article Preview
Top1 Introduction And Motivation
Cellular automata (CA) are one of the most popular and most researched models of discrete dynamical systems. Originally introduced as a mathematical model that captures high-level dynamic behavior of biological systems capable of self-reproduction, CA have been extensively studied in a great variety of application domains – primarily in modeling and simulation of complex physical, biological, social and/or socio-technical systems. However, CA have also been viewed as an abstraction of massively parallel computers. While most of the previous computer science research on CA and similar models has used those models as an abstraction for parallel hardware architectures, our agenda is to use these complex system models as an abstraction for open distributed environments at the software level.
More specifically, we would like to apply CA as an abstraction for autonomously executing local processes that are coupled to and interacting with one another and possibly also with other aspects of their environment. Even when these individual processes are rather simple, their mutual interaction and synergy may potentially yield a highly complex and difficult to predict long-term global behavior. This property, namely, that the behavior of the “whole” (the entire system) cannot be easily deduced from the simple and well-understood behaviors of the “pieces” (individual components), is a hallmark property of both nonlinear dynamical systems in physical sciences and distributed systems in computer science.
It has been observed that large-scale computational and communication infrastructures in general, and multi-agent systems (MAS) of software, robotic and other varieties in particular, are getting increasingly physically and logically distributed, heterogeneous, and complex. We are particularly interested in modeling and simulation of large-scale MAS made of relatively simple autonomous software or other types of agents, with the focus on collective dynamics and emerging behavior of such systems (Tosic, 2005). Research on MAS heavily draws on the existing theories, tools and methodologies from AI, software engineering and distributed computing. We would like to contribute to the more thorough understanding and better design of large-scale MAS some ideas, paradigms and tools from another scientific discipline, namely, discrete dynamical systems – especially those models of dynamical systems that are based on communicating automata.
To formally analyze, predict and verify properties of complex distributed systems, various formal models based on different types of communicating automata have been proposed (see, e.g., Lynch, 1996). Among a broad variety of such formal automata based models, we particularly like the idea of using models based on classical cellular automata for modeling and analysis of large-scale distributed infrastructures and multi-agent systems; reasons behind this preference include CA’s descriptive simplicity, mathematical elegance, ease of computer simulations and wealth of “prior art” insofar as rich history multi-faceted research on various properties of CA dynamics spanning nearly half a century.
What are, then, the important properties of large-scale distributed computational and communication systems in general, and MAS in particular, that can be adequately captured by the classical CA and CA-like models? Let’s consider a cellular automaton from a MAS perspective. Studying the global dynamics of a CA then translates into an exploration of the global behavior of a multi-agent system when (i) the individual agent behaviors are fixed, (ii) the pattern of multi-agent interaction (“network topology”) is fixed, and (iii) both the individual agent behaviors and the interaction patterns among the agents are highly regular and uniform (i.e., homogeneous) across the entire system. In particular, CA and other related models capture the critically important MAS features of the locality of interaction among the agents, and the bounded speed of information and impact propagation.
Several modifications of the basic CA model along different dimensions can be readily argued to provide appropriate abstractions for large-scale distributed computing and, in particular, for large-scale MAS. We have identified the following four as the most relevant and important:
– heterogeneity of the cellular/graph automata in terms of (i) the individual agent behaviors and (ii) the inter-agent interaction pattern, in contrast to the strict homogeneity of the classical CA in both these respects;
– model of inter-agent communication insofar as whether the agents locally compute synchronously or asynchronously, and whether they interact (communicate) with one another synchronously or asynchronously;