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$, sous l'hypothèse d'\emph{équité globale}. Nous présentons une solution optimale qui nécessite seulement $P$ états. Pour le nommage, il exist une solution avec $\frac{3}{2}P$ états par agent, sous é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}.
Origine : Fichiers produits par l'(les) auteur(s)