Computing with Pavlovian Populations

Abstract : Population protocols have been introduced by Angluin et {al.} as a model of networks consisting of very limited mobile agents that interact in pairs but with no control over their own movement. A collection of anonymous agents, modeled by finite automata, interact pairwise according to some rules that update their states. Predicates on the initial configurations that can be computed by such protocols have been characterized as semi-linear predicates. In an orthogonal way, several distributed systems have been termed in literature as being realizations of games in the sense of game theory. We investigate under which conditions population protocols, or more generally pairwise interaction rules, correspond to games. We show that restricting to asymetric games is not really a restriction: all predicates computable by protocols can actually be computed by protocols corresponding to games, i.e. any semi-linear predicate can be computed by a Pavlovian population multi-protocol.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-polytechnique.archives-ouvertes.fr/hal-00760778
Contributor : Olivier Bournez <>
Submitted on : Tuesday, December 4, 2012 - 2:01:30 PM
Last modification on : Tuesday, November 19, 2019 - 12:25:55 PM
Long-term archiving on: Tuesday, March 5, 2013 - 3:52:24 AM

File

submitted.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00760778, version 1

Citation

Olivier Bournez, Jérémie Chalopin, Johanne Cohen, Xavier Koegler, Mikaël Rabie. Computing with Pavlovian Populations. Principles of Distributed Systems - 15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011. Proceedings, 2011, France. pp.409-420. ⟨hal-00760778⟩

Share

Metrics

Record views

405

Files downloads

148