Comptage et nommage simples et efficaces dans les protocoles de populations symétriques

Nous améliorons les meilleurs résultats connus, en terme de nombre d'états d'un agent, pour les solutions aux problèmes du \emph{comptage} et du \emph{nommage} dans un modèle voisin des \emph{protocoles de populations}. Pour le comptage, étant donnée une borne $P$ sur le nombre d'agents, le meilleur résultat connu était $\frac{3}{2}P$ états, sous l'hypothèse d'\emph{équité globale}. Nous présentons une solution qui nécessite seulement $P$ états. Pour le nommage, il existe une solution avec $\frac{3}{2}P$ états par agent, sous l'hypothèse d'équité globale. Nous présentons une solution à $P$ états, ainsi qu'une solution à $2P$ états sous \emph{équité faible} (les deux solutions sont totalement \emph{auto-stabilisantes}). Enfin, nous décrivons un protocole de \emph{comptage approximatif} nécessitant $O(\log{(P)})$ états et un protocole de \emph{nommage consécutif minimal}.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00948186
Author Beauquier, Joffroy, Burman, Janna, Claviére, Simon
Maintainer CCSD
Last Updated May 5, 2026, 11:54 (UTC)
Created May 5, 2026, 11:54 (UTC)
Identifier hal-00948186
Language fr
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire de Recherche en Informatique (LRI) ; Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
creator Beauquier, Joffroy
date 2014-02-17T00:00:00
harvest_object_id 185244cb-7aa9-4cb0-9255-22983b26adaf
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2024-02-10T00:00:00
set_spec type:REPORT