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:Incollection
Entered by:ichatz
TitlePopulation Protocols and Related Models
Bibtex cite IDRACTI-RU1-2011-10
Booktitle Theoretical Aspects of Distributed Computing in Sensor Networks
Series Monographs in Theoretical Computer Science. An EATCS Series, 201
Year published 2011
Month January
Number 928
Pages 109-159
Chapter 5
Publisher Springer-Verlag
ISBN 978-3-642-14848-4
DOI 10.1007/978-3-642-14849-1_5
This is a joint work with Ioannis Chatzigiannakis and Othon Michail. We discuss here the population protocol model and most of its well-known extensions. The population protocol model aims to represent sensor networks consisting of tiny computational devices with sensing capabilities that follow some unpredictable and uncontrollable mobility pattern. It adopts a minimalistic approach and, thus, naturally computes a quite restricted class of predicates and exhibits almost no fault-tolerance. Most recent approaches make extra realistic and implementable assumptions, in order to gain more computational power and/or speed-up the time to convergence and/or improve fault-tolerance. In particular, the mediated population protocol model, the community protocol model, and the PALOMA model, which are all extensions of the population protocol model, are thoroughly discussed. Finally, the inherent difficulty of verifying the correctness of population protocols that run on complete communication graphs is revealed, but a promising algorithmic solution is presented.
Spirakis, Paul
Michail, Othon
Chatzigiannakis, Ioannis
tasn.pdf (main file)
Publication ID850