Cover Image

New models for population protocols /

Bibliographic Details
Main Author: Michail, Othon
Other Authors: Chatzigiannakis, Ioannis, Spirakis, P. G. (Paul G.), 1955-
Format: eBook
Language:English
Published: [San Rafael, Calif.] : Morgan & Claypool, [2011]
Series:Synthesis lectures on distributed computing theory ; #6.
Subjects:
Electronic data processing > Distributed processing > Mathematical models.
Wireless sensor networks > Mathematical models.
Electronic books.
Online Access:Connect to the full text of this electronic book
Table of 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
  • 3-state 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.