Titre : On trustful population protocols
Exposant : Mikael Rabie
Résumé : 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, agents are 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 with finitely many states, and when agents can possibly be arbitrary Turing machines. We also provide some time complexity considerations.