Design and Analysis of Distributed Averaging with Quantized Communication

Résumé : Nous allons nous intéresser à un réseau dont les nœuds, ou agents, ont des valeurs initiales. Nous souhaitons concevoir un algorithme ayant pour objectif la convergence vers une valeur qui est la plus proche possible de la moyenne de toutes les valeurs initiales des nœuds. Cette algorithme est basée sur les interaction entre les nœuds, où un nœud interagit avec un autre nœud si ils sont voisins dans le graphe. Un tel algorithme est communément appelé "moyenne distribuée". L'objectif de cet article est d'étudier les performances d'une sous-classe d'algorithmes déterministes de calcul de la moyenne distribuée, où l'échange d'informations entre les nœuds voisins est soumis à la quantification uniforme. Avec une telle quantification, la moyenne précise ne peut être atteinte (sauf dans des cas exceptionnels), mais une valeur proche d'elle peut être atteinte. Cette valeur est appelée consensus quantifié. Nous montrons dans ce papier que, dans un temps fini, soit tous les agents parviennent à un consensus quantifié où la valeur de consensus est le plus grand entier qui n'est pas supérieur à la moyenne de leurs valeurs initiales; ou soit tous les agents cyclent dans un petit voisinage autour de la moyenne, en fonction des conditions initiales. Dans ce dernier cas, il est démontré que le voisinage peut être rendue arbitrairement faible en ajustant les paramètres de l'algorithme de manière distribuèe.
Type de document :
Rapport
[Research Report] RR-8501, Inria. 2014, pp.33
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00960891
Contributeur : Mahmoud El Chamie <>
Soumis le : samedi 13 septembre 2014 - 22:10:57
Dernière modification le : samedi 27 janvier 2018 - 01:31:42
Document(s) archivé(s) le : dimanche 14 décembre 2014 - 10:25:06

Fichiers

RR-8501.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00960891, version 2
  • ARXIV : 1403.4696

Collections

Citation

Mahmoud El Chamie, Ji Liu, Tamer Başar. Design and Analysis of Distributed Averaging with Quantized Communication. [Research Report] RR-8501, Inria. 2014, pp.33. 〈hal-00960891v2〉

Partager

Métriques

Consultations de la notice

139

Téléchargements de fichiers

95