Reducing Communication Overhead for Average Consensus

Résumé : Le consensus de moyenne est un protocole itératif où les nœuds d'un réseau, ayant chacun une estimation initiale, exécutent un algorithme distribué pour calculer la moyenne de ces estimations en utilisant uniquement les communication locales. A chaque itération, les nœuds échangent leurs estimations avec leurs voisins. Ces estimations seront remplacées par la moyenne pondérée de celles reçues. La convergence du consensus de moyenne est asymptotique et la mise en œuvre d'un protocole de terminaison est difficile lorsque les nœuds ne connaissent pas l'estimation global (par exemple, le diamètre du réseau ou le nombre de nœuds). Dans ce rapport, nous intéressons à la réduction du taux de messages envoyés dans le réseau quand les estimations deviennent proche du consensus. Nous présentons un algorithme de consensus de moyenne totalement distribué, où les nœuds envoient plus de messages lorsque la différence entre leurs estimations est grande et moins de messages lorsque le système est à peu prés convergeant. La convergence du système est garantie d'être proche de la vraie moyenne et le coût des communications est fortement réduit.
Type de document :
Rapport
[Research Report] RR-8025, INRIA. 2012, pp.22
Liste complète des métadonnées

https://hal.inria.fr/hal-00720687
Contributeur : Mahmoud El Chamie <>
Soumis le : mercredi 1 août 2012 - 11:33:31
Dernière modification le : samedi 27 janvier 2018 - 01:31:44
Document(s) archivé(s) le : vendredi 2 novembre 2012 - 02:30:37

Fichier

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

Identifiants

  • HAL Id : hal-00720687, version 2

Collections

Citation

Mahmoud El Chamie, Giovanni Neglia, Konstantin Avrachenkov. Reducing Communication Overhead for Average Consensus. [Research Report] RR-8025, INRIA. 2012, pp.22. 〈hal-00720687v2〉

Partager

Métriques

Consultations de la notice

508

Téléchargements de fichiers

161