Description 
1 online resource (xvi, 140 pages) : illustrations 
Series 
Synthesis lectures on distributed computing theory, 21551634 ; #6 

Synthesis lectures on distributed computing theory ; #6. 21551626

Contents 
1. Population protocols  Introduction  A formal model  Stable computation  Computational complexity  Overview of the content  Organization of the text  Exercises 

2. The computational power of population protocols  Semilinear sets and Presburger arithmetic  Semilinear predicates are stably computable  Stably computable predicates are semilinear  Exercises 

3. Enhancing the model  Introduction  Composition of protocols: stabilizing inputs  Probabilistic population protocols  Epidemics  3state approximate majority protocol  Virtual register machine simulation  Community protocols  The model  Computational power  Exercises 

4. Mediated population protocols and symmetry  Symmetric nondeterministic space (n2)  Stable computation  Predicates on input assignments  Stably decidable network properties  Weakly connected graphs  Graphs not even weakly connected  Exercises 

5. Passively mobile machines that use restricted space  The model and the power of log space  A first inclusion for PMSPACE (log n)  Assigning unique ids by reinitiating computation  A better inclusion for PMSPACE (log n)  An exact characterization for PMSPACE (log n)  Below log space, above log space and a space hierarchy  Behavior of the PM model for space o(log log n)  The logarithmic predicate  Exercises 

6. Conclusions and open research directions  Conclusions  Open research directions  Bibliography  Acronyms  Authors' biographies 
Summary 
Wireless sensor networks are about to be part of everyday life. Homes and workplaces capable of selfcontrolling and adapting airconditioning for different temperature and humidity levels, sleepless forests ready to detect and react in case of a fire, vehicles able to avoid sudden obstacles or possibly able to selforganize routes to avoid congestion, and so on, will probably be commonplace in the very near future. Mobility plays a central role in such systems and so does passive mobility, that is, mobility of the network stemming from the environment itself. The population protocol model was an intellectual invention aiming to describe such systems in a minimalistic and analysisfriendly way. Having as a startingpoint the inherent limitations but also the fundamental establishments of the population protocol model, we try in this monograph to present some realistic and practical enhancements that give birth to some new and surprisingly powerful (for these kind of systems) computational models 
Notes 
Series from website 
Bibliography 
Includes bibliographical references (pages 129136) 
Subject 
Electronic data processing  Distributed processing  Mathematical models.


Wireless sensor networks  Mathematical models.

Form 
Electronic book

Author 
Chatzigiannakis, Ioannis.


Spirakis, P. G. (Paul G.), 1955

ISBN 
1608455904 (electronic bk.) 

9781608455904 (electronic bk.) 
