Skip to Main content Skip to Navigation

Non-deterministic Population Protocols (Extended Version)

Joffroy Beauquier 1, 2 Janna Burman 1, 2, * Laurent Rosaz 1 Brigitte Rozoy 1 
* Corresponding author
2 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : In this paper we show that, in terms of generated output languages, non-deterministic \textit{population protocols} are strictly more powerful than deterministic ones. Analyzing the reason for this negative result, we propose two slightly enhanced models, in which non-deterministic population protocols can be \emph{exactly} simulated by deterministic ones. First, we consider a model in which interactions are not only between couples of agents, but also between triples and in which non-uniform initial states are allowed. We generalize this transformation and we prove a general property for a model with interactions between any number of agents. Second, we simulate any non-deterministic population protocol by a deterministic one in a model where a \emph{configuration} can have an \textit{empty output}. Non-deterministic and deterministic population protocols are then compared in terms of inclusion of their output languages, that is, in terms of solvability of problems. Two transformations, which realize this inclusion, are presented. The first one uses (again) the natural model with interactions of triples, but does not need non-uniform initial states. As before, this result is generalized for the natural model with interactions between any number of agents. The second transformation is a parameterized one with parameters depending on the transition graph of the considered non-deterministic protocol and on the population. Note that the transformations in the paper apply to a whole class of non-deterministic population protocols (for a proposed model), in contrast with the transformations proposed in previous works, which apply only to a specific sub-class of protocols (satisfying a so called ''elasticity'' condition).
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Janna Burman Connect in order to contact the contributor
Submitted on : Monday, October 1, 2012 - 6:10:18 PM
Last modification on : Sunday, June 26, 2022 - 11:57:02 AM
Long-term archiving on: : Wednesday, January 2, 2013 - 9:20:08 AM


Files produced by the author(s)


  • HAL Id : hal-00736261, version 2


Joffroy Beauquier, Janna Burman, Laurent Rosaz, Brigitte Rozoy. Non-deterministic Population Protocols (Extended Version). [Research Report] 2012. ⟨hal-00736261v2⟩



Record views


Files downloads