Non-deterministic Population Protocols (Extended Version) - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

Non-deterministic Population Protocols (Extended Version)

Résumé

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).
Fichier principal
Vignette du fichier
determinizationPP_long.pdf (157.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00736261 , version 1 (27-09-2012)
hal-00736261 , version 2 (01-10-2012)

Identifiants

  • HAL Id : hal-00736261 , version 1

Citer

Joffroy Beauquier, Janna Burman, Laurent Rosaz, Brigitte Rozoy. Non-deterministic Population Protocols (Extended Version). [Research Report] 2012. ⟨hal-00736261v1⟩
172 Consultations
192 Téléchargements

Partager

Gmail Facebook X LinkedIn More