Design and Analysis of Distributed Averaging With Quantized Communication
| Autor: | Tamer Basar, Mahmoud El Chamie, Ji Liu |
|---|---|
| Přispěvatelé: | Models for the performance analysis and the control of networks (MAESTRO), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Coordinated Science Laboratory (CSL), University of Illinois System, Inria |
| Rok vydání: | 2016 |
| Předmět: |
Lyapunov function
Mathematical optimization 0209 industrial biotechnology quantized consensus Quantization effects 02 engineering and technology Topology Quantization (physics) symbols.namesake 020901 industrial engineering & automation FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Cyclic system Electrical and Electronic Engineering Mathematics - Optimization and Control Connectivity Mathematics Lyapunov stability distributed averaging Finite-state machine cycle Probabilistic logic Computer Science Applications Nonlinear system Optimization and Control (math.OC) Control and Systems Engineering symbols Algorithm design 020201 artificial intelligence & image processing quantization [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] finite state automata Lyapunov Function |
| Zdroj: | CDC [Research Report] RR-8501, Inria. 2014, pp.33 IEEE 53rd Annual Conference on Decision and Control (CDC 2014) IEEE 53rd Annual Conference on Decision and Control (CDC 2014), Dec 2014, Los Angeles, United States. pp.3860-3865, ⟨10.1109/CDC.2014.7039988⟩ |
| ISSN: | 1558-2523 0018-9286 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|