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:
TitleStably Decidable Graph Languages by Mediated Population Protocols
Bibtex cite IDRACTI-RU1-2010-26
Booktitle 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Series LNCS
Year published 2010
Month September
Volume 6366/2010
Pages 252-266
Publisher Springer-Verlag Berlin Heidelberg
Location New York City, USA
DOI 10.1007/978-3-642-16023-3_21
We work on an extension of the Population Protocol model of Angluin et al. that allows edges of the communication graph, G, to have states that belong to a constant size set. In this extension, the so called Mediated Population Protocol model (MPP), both uniformity and anonymity are preserved. We study here a simplified version of MPP in order to capture MPP's ability to stably compute graph properties. To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph property is not computable if we allow disconnected communication graphs. As a result, we focus on studying (at least) weakly connected communication graphs only and give several examples of computable properties in this case. To do so, we also prove that the class of computable properties is closed under complement, union and intersection operations. Node and edge parity, bounded out-degree by a constant, existence of a node with more incoming than outgoing neighbors, and existence of some directed path of length at least k=O(1) are some examples of properties whose computability is proven. Finally, we prove the existence of symmetry in two specific communication graphs and, by exploiting this, we prove that there exists no protocol, whose states eventually stabilize, to determine whether G contains some directed cycle of length 2.
Chatzigiannakis, Ioannis
Michail, Othon
Spirakis, Paul
gl-sss10.pdf (main file)
Publication ID769