Distributed Weight Selection in Consensus Protocols by Schatten Norm Minimization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

Distributed Weight Selection in Consensus Protocols by Schatten Norm Minimization

Résumé

In average consensus protocols, nodes in a network perform an iterative weighted average of their estimates and those of their neighbors. The protocol converges to the average of initial estimates of all nodes found in the network. The speed of convergence of average consensus protocols depends on the weights selected on links (to neighbors). We address in this paper how to select the weights in a given network in order to have a fast speed of convergence for these protocols. We approximate the problem of optimal weight selection by the minimization of the Schatten p-norm of a matrix with some constraints related to the connectivity of the underlying network. We then provide a totally distributed gradient method to solve the Schatten norm optimization problem. By tuning the parameter p in our proposed minimization, we can simply trade-off the quality of the solution (i.e. the speed of convergence) for communication/computation requirements (in terms of number of messages exchanged and volume of data processed). Simulation results show that our approach provides very good performance already for values of p that only needs limited information exchange. The weight optimization iterative procedure can also run in parallel with the consensus protocol and form a joint consensus-optimization procedure.
Dans les protocoles de consensus, les nœuds d'un réseau calculent itérativement une moyenne pondérée de leurs mesures et celles de leurs voisins. Le protocole converge vers la moyenne des mesures initiales de tous les nœuds présents dans le réseau. La vitesse de convergence des protocoles de consensus dépend des poids sélectionnés sur les liens entre voisins. Nous abordons dans cet article la question suivante : comment choisir les poids dans un réseau donné afin d'avoir une plus grande vitesse de convergence du protocole? Nous approchons le problème de la sélection optimale de poids avec un problème de minimisation de la p-norme de Schatten. Ce dernier est résolu de manière totalement distribuée grâce à une méthode du gradient. Selon la valeur du paramètre p, nous pouvons trouver un compromis entre la qualité de la solution (c'est-à-dire la vitesse de convergence) et les coût en termes de communication et calcul (e.g. nombre de messages échangés et volume de données traitées). Les résultats des simulations montrent que notre approche fournit une très bonne performance même avec un échange d'informations limité. La procédure d'optimisation des poids peut également se dérouler en simultané avec le protocole de consensus.
Fichier principal
Vignette du fichier
RR-8078.pdf (750.78 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00738249 , version 1 (03-10-2012)
hal-00738249 , version 2 (06-11-2013)
hal-00738249 , version 3 (17-07-2014)

Identifiants

  • HAL Id : hal-00738249 , version 1

Citer

Mahmoud El Chamie, Giovanni Neglia, Konstantin Avrachenkov. Distributed Weight Selection in Consensus Protocols by Schatten Norm Minimization. [Research Report] RR-8078, 2012, pp.23. ⟨hal-00738249v1⟩

Collections

INRIA-RRRT
413 Consultations
610 Téléchargements

Partager

Gmail Facebook X LinkedIn More