Colonies of Synchronizing Agents

We propose a modelling framework and computational paradigm called Colonies of Synchronizing Agents (CSAs) inspired by the intracellular and intercellular mechanisms present in biological tissue. The proposed model is based on a multiset of agents present in a common environment. Each agent has a local state, stored in the form of a multiset of atomic objects, which is updated by global multiset rewriting rules either asynchronously or in synchrony with another agent. We first define the model, then study its computational power, considering trade-offs between internal rewriting (i.e., intracellular mechanism) and synchronization among the agents (i.e., intercellular mechanisms). We also investigate dynamic properties of CSAs, including behavioral robustness (ability to generate a core behavior despite agents or rule failure) and safety of synchronization (ability for an agent to synchronize with another agent, whenever needed). This is the preliminary version of a paper that was published in Proceedings of International Workshop Automata for Cellular and Molecular Computing, Computer and Automation Research Institute of the Hungarian Academy of Sciences, 2007.