Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2009-07-17
Computer Science
Distributed, Parallel, and Cluster Computing
Submitted to Applied Mathematics and Computation. 2009
Scientific paper
Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement. A population protocol corresponds to a collection of anonymous agents, modeled by finite automata, that interact with one another to carry out computations, by updating their states, using some rules. Their computational power has been investigated under several hypotheses but always when restricted to finite size populations. In particular, predicates stably computable in the original model have been characterized as those definable in Presburger arithmetic. We study mathematically the convergence of population protocols when the size of the population goes to infinity. We do so by giving general results, that we illustrate through the example of a particular population protocol for which we even obtain an asymptotic development. This example shows in particular that these protocols seem to have a rather different computational power when a huge population hypothesis is considered.
Bournez Olivier
Chassaing Philippe
Cohen Johanne
Gerin Lucas
Koegler Xavier
No associations
LandOfFree
On the Convergence of Population Protocols When Population Goes to Infinity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Convergence of Population Protocols When Population Goes to Infinity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Convergence of Population Protocols When Population Goes to Infinity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-111075