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

Résumé : 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}.
Type de document :
Rapport
[Rapport de recherche] 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00948186
Contributeur : Janna Burman <>
Soumis le : mercredi 7 mai 2014 - 14:15:25
Dernière modification le : jeudi 11 janvier 2018 - 06:20:11
Document(s) archivé(s) le : lundi 10 avril 2017 - 19:58:45

Fichier

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

Identifiants

  • HAL Id : hal-00948186, version 3

Citation

Joffroy Beauquier, Janna Burman, Simon Claviére. Comptage et nommage simples et efficaces dans les protocoles de populations symétriques. [Rapport de recherche] 2014. 〈hal-00948186v3〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

85