Non-deterministic Population Protocols (Extended Version)

Joffroy Beauquier 1, 2 Janna Burman 1, 2, * Laurent Rosaz 1 Brigitte Rozoy 1
* Auteur correspondant
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).
Type de document :
Rapport
[Research Report] 2012
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00736261
Contributeur : Janna Burman <>
Soumis le : lundi 1 octobre 2012 - 18:10:18
Dernière modification le : lundi 9 avril 2018 - 16:58:02
Document(s) archivé(s) le : mercredi 2 janvier 2013 - 09:20:08

Fichier

determinizationPP.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00736261, version 2

Collections

Citation

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

Partager

Métriques

Consultations de la notice

277

Téléchargements de fichiers

100