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:
TitleBrief Announcement: Decidable Graph Languages by Mediated Population Protocols
Bibtex cite IDRACTI-RU1-2009-98
Booktitle 23rd International Symposium on Distributed Computing
Year published 2009
Location Spain
Note to appear
We work on an extension of the Population Protocol model of Angluin et al. [1] 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) [2,3], both uniformity and anonymity are preserved.We here study a simplified version of MPP, the Graph Decision Mediated Population Protocol model (GDM), in order to capture MPP's ability to decide graph languages. We also prove some first impossibility results both for weakly connected and possibly disconnected communication graphs.
Chatzigiannakis, Ioannis
Michail, Othon
Spirakis, Paul
fulltext.pdf (main file)
Publication ID784