Skip to Main content Skip to Navigation
Reports

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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LIFL - Laboratoire d'Informatique Fondamentale de Lille, LRI - Laboratoire de Recherche en Informatique
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

https://hal.inria.fr/hal-00736261
Contributor : Janna Burman <>
Submitted on : Monday, October 1, 2012 - 6:10:18 PM
Last modification on : Thursday, July 8, 2021 - 3:48:43 AM
Long-term archiving on: : Wednesday, January 2, 2013 - 9:20:08 AM

File

determinizationPP.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00736261, version 2

Citation

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

Share

Metrics

Record views

371

Files downloads

256