Skip to Main content Skip to Navigation
Reports

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}.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00948186
Contributor : Janna Burman <>
Submitted on : Wednesday, May 7, 2014 - 2:15:25 PM
Last modification on : Wednesday, September 16, 2020 - 4:57:40 PM
Long-term archiving on: : Monday, April 10, 2017 - 7:58:45 PM

File

Algotel_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00948186, version 3

Collections

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⟩

Share

Metrics

Record views

227

Files downloads

249