New Models for Population Protocols

Wireless sensor networks are about to be part of everyday life. Homes and workplaces capable of self-controlling and adapting air-conditioning 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 self-organize 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 analysis-friendly way. Having as a starting-point 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. Table of Contents: Population Protocols / The Computational Power of Population Protocols / Enhancing the model / Mediated Population Protocols and Symmetry / Passively Mobile Machines that Use Restricted Space / Conclusions and Open Research Directions / Acronyms / Authors' Biographies

Othon Michail, born in 1984, obtained his Diploma and his MSc in Computer Science & Technology from the Department of Computer Engineering & Informatics of the University of Patras in 2007 and 2009, respectively. He recently (September 2010) obtained his Ph.D. from the same department under the supervision of Prof. Dr. Paul Spirakis. The title of his thesis is “New Models for Population Protocols”. He is currently a member of the Research Unit 1 of the RACTI (since April 2009). His research interests include Theory of Computation in new models of computation (like wireless sensor networks and, in particular, population protocols), Computational Complexity, and Algorithms. Ioannis Chatzigiannakis obtained his Ph.D. from the Department of Computer Engineering & Informatics of the University of Patras in 2003. He is currently Adjunct Faculty at the Computer Engineering & Informatics Department of the University of Patras (since October 2005). He is the Director of the Research Unit 1 of RACTI (since July 2007). He has coauthored over 70 scientific publications. His main research interests include distributed and mobile computing, wireless sensor networks, algorithm engineering and software systems. He has served as a consultant to major Greek computing industries. He is the Secretary of the European Association for Theoretical Computer Science since July 2008. Paul Spirakis, born in 1955, obtained his Ph.D. from Harvard University, in 1982. He is currently the Director of the RACTI and a Full Professor in the Patras University, Greece. He was acknowledged between the top 50 scientists worldwide in Computer Science with respect to “The best Nurturers in Computer Science Research”, published by B. Kumar and Y.N. Srikant, ACM Data Mining, 2005. His research interests are Algorithms and Complexity and inter[1]action of Complexity and Game Theory. Paul Spirakis has extensively published in most of the important Computer Science journals and most of the significant refereed conferences contributing to over 300 scientific publications. He was elected unanimously as one of the two Vice Presidents of the Council of the EATCS. He is a member of the ACM Europe Council and also a member of Academia Europaea.