TY - GEN
T1 - Computing with Pavlovian populations
AU - Bournez, Olivier
AU - Chalopin, Jérémie
AU - Cohen, Johanne
AU - Koegler, Xavier
AU - Rabie, Mikaël
PY - 2011/12/26
Y1 - 2011/12/26
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-642-25873-2_28
DO - 10.1007/978-3-642-25873-2_28
M3 - Conference contribution
AN - SCOPUS:84055222606
SN - 9783642258725
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 409
EP - 420
BT - Principles of Distributed Systems - 15th International Conference, OPODIS 2011, Proceedings
T2 - 15th International Conference on Principles of Distributed Systems, OPODIS 2011
Y2 - 13 December 2011 through 16 December 2011
ER -