Mobile agent systems and cellular automata

摘要

The purpose of this article (based on an earlier draft available as technical report: Gruner S, Mobile agent systems and cellular automata. LaBRI Research Reports, 2006) is to make a step towards uniting the paradigms of cellular automata and mobile agents, thus consequentially the fields of artificial life and multi agent systems, which have significant overlap but are still largely perceived as separate fields. In Chalopin et al. (Mobile agent algorithms versus message passing algorithms, pp. 187-201, 2006) the equivalent power of classical distributed algorithms and mobile agent algorithms was demonstrated for asynchronous systems with interleaving semantics under some further constraints and assumptions. Similar results are still being sought about mobile agent systems and distributed systems under other constraints and assumptions in search of a comprehensive general theory of these topics. This article investigates the relationship between mobile agent systems and a generalized form of cellular automata. With a particular notion of local equivalence, a cellular automaton can be translated into a mobile agent system and vice versa. The article shows that if the underlying network graph is finite, then the degree of pseudo-synchrony of the agent system simulating the cellular automaton can be made arbitrarily high, even with an only small number of active agents. As a possible consequence of this theoretical result, the Internet might be used in the future to implement large cellular automata of almost arbitrary topology.