%0 Book Section %1 series/eatcs/Spirakis11 %A Spirakis, Paul G. %B Theoretical Aspects of Distributed Computing in Sensor Networks %D 2011 %E Nikoletseas, Sotiris E. %E Rolim, José D. P. %I Springer %K distributed populationprotocols %P 109-159 %T Population Protocols and Related Models. %U http://dblp.uni-trier.de/db/series/eatcs/sensor2011.html#Spirakis11 %X Abstract 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. %@ 978-3-642-14849-1

@incollection{series/eatcs/Spirakis11, abstract = {Abstract 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.}, added-at = {2019-02-01T13:18:48.000+0100}, author = {Spirakis, Paul G.}, biburl = {https://www.bibsonomy.org/bibtex/22e0e49283f406c54f019ae01f8e291ca/paves_intern}, booktitle = {Theoretical Aspects of Distributed Computing in Sensor Networks}, crossref = {series/eatcs/Sensor2011}, description = {#survey}, editor = {Nikoletseas, Sotiris E. and Rolim, José D. P.}, ee = {http://dx.doi.org/10.1007/978-3-642-14849-1_5}, interhash = {723d635cdbb15b74d055d4082d5ac605}, intrahash = {2e0e49283f406c54f019ae01f8e291ca}, isbn = {978-3-642-14849-1}, keywords = {distributed populationprotocols}, pages = {109-159}, publisher = {Springer}, series = {Monographs in Theoretical Computer Science. An EATCS Series}, timestamp = {2019-02-01T13:18:48.000+0100}, title = {Population Protocols and Related Models.}, url = {http://dblp.uni-trier.de/db/series/eatcs/sensor2011.html#Spirakis11}, year = 2011 }