Thesis Defense Seminar - Demetri Spanos

Title: "An Approach to Designing Dynamics for Distributed Coordination"

Many systems comprised of interconnected sub-units exhibit coordinated behaviors; social groups, networked computers, financial markets, and numerous biological systems come to mind.

There has been long-standing interest in developing a scientific understanding of coordination, both for explanatory power in the natural and social sciences, but also for \emph{constructive} power in engineering and applied sciences. This thesis is an abstract study of coordination, focused on developing a systematic ``design theory" for producing interconnected systems with specifiable coordinated behavior; this is in contrast to much previous work on this subject, in which the design component has been primarily ad-hoc.

The main theoretical contribution of the work is a geometric formalism in which to cast distributed systems. This has numerous advantages, and ``naturally" parametrizes a wide class of distributed interaction mechanisms in a uniform way. We make use of this framework to present a model for distributed optimization, and we introduce the \emph{distributed gradient} as a general design tool for synthesizing dynamics for distributed systems. The distributed optimization model is a useful abstraction in its own right, and motivates a definition for a distributed extremum. As one might expect, the distributed gradient is zero at a distributed extremum, and the dynamics of a distributed gradient flow must converge to a distributed extremum. This forms the basis for a wide variety of designs, and we are in fact able to recover a widely studied distributed averaging algorithm as a very special case. We also present several other applications, ranging from standard network coordination tasks (clock synchronization and leader election) to more exotic tasks like distributed graph coloring, account balancing, and various statistical computations.