Design and Analysis of Distributed Averaging with Quantized Communication
Résumé
Consider a network whose nodes have some initial values, and it is desired to design an algorithm that builds on neighbor to neighbor interactions with the ultimate goal of convergence to the average of all initial node values or to some value close to that average. Such an algorithm is called generically "distributed averaging," and our goal in this paper is to study the performance of a subclass of deterministic distributed averaging algorithms where the information exchange between neighboring nodes (agents) is subject to uniform quantization. With such quantization, convergence to the precise average cannot be achieved in general, but the convergence would be to some value close to it, called quantized consensus. Using Lyapunov stability analysis, we characterize the convergence properties of the resulting nonlinear quantized system. We show that in finite time and depending on initial conditions, the algorithm will either cause all agents to reach a quantized consensus where the consensus value is the largest quantized value not greater than the average of their initial values, or will lead all variables to cycle in a small neighborhood around the average. In the latter case, we identify tight bounds for the size of the neighborhood and we further show that the error can be made arbitrarily small by adjusting the algorithm's parameters in a distributed manner.
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...