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:
TitleDecidable Graph Languages by Mediated Population Protocols
Bibtex cite IDRACTI-RU1-2009-24
Booktitle 23rd International Symposium on Distributed Computing (DISC 2009)
Series Lecture Notes in Computer Science
Year published 2009
Month September
Volume 5805
Pages 239-240
Publisher Springer-Verlag, LNCS
Location Elche/Elx, Spain
Keywords population protocols diffuse computation,decidability,communicating automata,finite automata
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 here study a simplified version of MPP, the Graph Decision Mediated Population Protocol model (GDM), in order to capture MPP's ability to decide (stably compute) graph languages (sets of communication graphs). To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph language is undecidable if we allow disconnected communication graphs. As a result, we focus on studying the computational limits of the GDM model in (at least) weakly connected communication graphs only and give several examples of decidable graph languages in this case. To do so, we also prove that the class of decidable graph languages 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 decidability is proven. To prove the decidability of graph languages we provide protocols (GDMs) for them and exploit the closure results. Finally, we prove the existence of symmetry in two specific communication (sub)graphs which we believe is the first step towards the proof of impossibility results in the GDM model. In particular, we prove that there exists no GDM, whose states eventually stabilize, to decide whether G contains some directed cycle of length 2 (2-cycle).
Chatzigiannakis, Ioannis
Michail, Othon
Spirakis, Paul
disc09 - BA - CMS.pdf (main file)
Disc09 - TechReport - CMS.pdf
Publication ID667