The computational power of simple protocols for self-awareness on graphs

Abstract. We explore the capability of a network of extremely lim-ited computational entities to decide properties about any of its sub-networks. We consider that the underlying network of the interacting entities (devices, agents, processes etc.) is modeled by a complete in-teraction graph and we devise simple graph protocols that can decide properties of some input subgraph provided by some preprocessing on the network. The agents are modeled as finite-state automata and run the same global graph protocol. Each protocol is a fixed size grammar, that is, its description is independent of the size (number of agents) of the network. This size is not known by the agents. We propose a simple model, the Mediated Graph Protocol (MGP) model, similar to the Pop-ulation Protocol model of Angluin et al., in which each network link is characterized by a state taken from a finite set. This state can be used and updated during each interaction between the corresponding agents. We provide some interesting properties of the MGP model among which is the ability to decide properties on stabilizing (initially changing for a finite number of steps) input graphs and we show that the MGP model has the ability to decide properties of disconnected input graphs. We show that the computational power within the connected components is fairly restricted. Finally, we give an exact characterization of the class GMGP, of graph languages decidable by the MGP model: it is equal to the class of graph languages decidable by a nondeterministic Turing Machine of linear space that receives its input graph by its adjacency matrix representation.