TY - GEN
T1 - Trustful population protocols
AU - Bournez, Olivier
AU - Lefevre, Jonas
AU - Rabie, Mikaël
PY - 2013/12/1
Y1 - 2013/12/1
N2 - Population protocols have been introduced by Angluin et al. as a model in which passively mobile anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. Stably computable predicates under this model have been characterized as exactly semi-linear predicates, that is to say exactly those definable in Presburger's arithmetic. We consider several variants of the models. In all these variants, the agents are called trustful : agents with a similar opinion that meet do not change their common opinion. We provide a characterization of the computational power of the obtained models, considering both the case when agents have finitely many states, and when agents can possibly be arbitrary Turing machines. We also provide some time complexity considerations.
AB - Population protocols have been introduced by Angluin et al. as a model in which passively mobile anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. Stably computable predicates under this model have been characterized as exactly semi-linear predicates, that is to say exactly those definable in Presburger's arithmetic. We consider several variants of the models. In all these variants, the agents are called trustful : agents with a similar opinion that meet do not change their common opinion. We provide a characterization of the computational power of the obtained models, considering both the case when agents have finitely many states, and when agents can possibly be arbitrary Turing machines. We also provide some time complexity considerations.
U2 - 10.1007/978-3-642-41527-2_31
DO - 10.1007/978-3-642-41527-2_31
M3 - Conference contribution
AN - SCOPUS:84893790859
SN - 9783642415265
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 447
EP - 461
BT - Distributed Computing - 27th International Symposium, DISC 2013, Proceedings
T2 - 27th International Symposium on Distributed Computing, DISC 2013
Y2 - 14 October 2013 through 18 October 2013
ER -