research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:ichatz
TitleThe Computational Power of Simple Protocols for Self-Awareness on Graphs
Bibtex cite IDRACTI-RU1-2011-34
Booktitle 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011)
Series Lecture Notes in Computer Science
Year published 2011
Month October
Volume 6976
Pages 135-147
Publisher Springer-Verlag Berlin Heidelberg
Location Grenoble, France
We explore the capability of a network of extremely limited computational entities to decide properties about any of its subnetworks. 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 nite-state automata and run the same global graph protocol. Each protocol is a xed 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 Population Protocol model of Angluin et al., in which each network link is characterized by a state taken from a nite 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 nite 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.
Chatzigiannakis, Ioannis
Michail, Othon
Nikolaou, Stavros
Spirakis, Paul
sss2011.pdf (main file)
Publication ID886