Computer Science – Computational Complexity
Scientific paper
2006-08-21
Computer Science
Computational Complexity
Combined version of OPODIS 2005 and PODC 2006 papers; submitted to Distributed Computing
Scientific paper
We consider the model of population protocols introduced by Angluin et al., in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way interactions in the all-pairs family of communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model. Removing the assumption of two-way interaction, we also consider several variants of the model in which agents communicate by anonymous message-passing where the recipient of each message is chosen by an adversary and the sender is not identified to the recipient. These one-way models are distinguished by whether messages are delivered immediately or after a delay, whether a sender can record that it has sent a message, and whether a recipient can queue incoming messages, refusing to accept new messages until it has had a chance to send out messages of its own. We characterize the classes of predicates stably computable in each of these one-way models using natural subclasses of the semilinear predicates.
Angluin Dana
Aspnes James
Eisenstat David
Ruppert Eric
No associations
LandOfFree
The computational power of population protocols 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 The computational power of population protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The computational power of population protocols will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-571886