Degree Type

Dissertation

Date of Award

2011

Degree Name

Doctor of Philosophy

Department

Electrical and Computer Engineering

First Advisor

Nicola Elia

Abstract

Distributed averaging, a canonical operation among many natural interconnected systems, has found applications in

a tremendous variety of applied fields, including statistical physics, signal processing, systems and control, communication and social science. As information exchange is a central part of distributed averaging systems, it is of practical as well as theoretical importance to understand various properties/limitations of those systems in

the presence of communication constraints and devise new algorithms

to alleviate those limitations.

We study the fragility of a popular distributed averaging algorithm

when the information exchange among the nodes is limited

by communication delays, fading connections and additive noise.

We show that the otherwise well studied and benign

multi-agent system can generate a collective global complex behavior.

We characterize this behavior, common to many natural and human-made interconnected systems, as a collective hyper-jump diffusion process and as a L\'{e}vy flights process in a special case. We further describe the mechanism for its emergence and predict its occurrence, under standard assumptions, by checking the Mean Square instability of a certain part of the system. We show that the strong connectivity property of the network topology guarantees that the complex behavior is global and manifested by all

the agents in the network, even though the source of uncertainty is localized. We provide novel computational analysis of the MS stability index under spatially invariant structures and gain certain qualitative as well as quantitative insights of the system.

We then focus on design of agents' dynamics to increase the robustness of distributed averaging system to topology variations. We provide a general structure of distributed averaging systems where individual agents are modeled by LTI systems. We show the problem of designing agents' dynamics for distributed averaging is equivalent to an $\mathcal{H}_{\infty}$ minimization problem. In this way, we could use tools from robust control theory to build the distributed averaging system where the design is fully distributed and scalable with the size of the network. It is also shown that the agents could be used in different fixed networks and networks with speical time varying interconnections.

We develop new iterative distributed averaging algorithms which allow

agents to compute the average quantity in the presence of

additive noise and random changing interconnections.

The algorithm relaxes several previous restrictive

assumptions on distributed averaging under

uncertainties, such as diminishing step size rule, doubly

stochastic weights, symmetric link switching styles, etc, and

introduces novel mechanism of network feedback to mitigate effects

of communication uncertainties on information aggregation.

Based on the robust distributed averaging algorithm, we propose continuous as well as discrete time computation models

to solve the distributed optimization problem where the objective function is formed by the summation of convex functions of the same variable.

The algorithm shows faster convergence speed than existing ones and

exhibits robustness to additive noise, which is the main source of limitation on algorithms based on convex mixing.

It is shown that agents with simple dynamics and gradient sensing abilities could collectively solve complicated convex optimization problems. Finally, we generalize this algorithm to build a general framework forconstrained convex optimization problems. This framework is shown to be particularly effective to derive solutions for distributed decision making problems and lead to a systems perspective for convex optimization.

DOI

https://doi.org/10.31274/etd-180810-1984

Copyright Owner

Jing Wang

Language

en

Date Available

2012-04-06

File Format

application/pdf

File Size

170 pages

Share

COinS