CaltechTHESIS
  A Caltech Library Service

Distributed gradient Ssystems and dynamic coordination

Citation

Spanos, Demetri Polychronis (2006) Distributed gradient Ssystems and dynamic coordination. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-06262006-171822

Abstract

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 economic sciences, and also for 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 the bulk of previous work on this subject, in which any design component has been primarily ad-hoc.

The main theoretical contribution of this 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 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 make use of our geometric model to introduce the notion of coordination capacity; intuitively, this is an upper bound on the "complexity" of coordination that is feasible given a particular distributed interaction structure. This gives intuitive results for local, distributed, and global control architectures, and allows formal statements to be made regarding the possibility of "solving" certain optimization problems under a particular distributed interaction model.

Finally, we present a number of applications to illustrate the theoretical approach presented; these range from "standard" distributed systems tasks (leader election and clock synchronization) to more exotic tasks like graph coloring, distributed account balancing, and distributed statistical computations.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:coordination dynamics; distributed coordination; distributed systems
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Control and Dynamical Systems
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Murray, Richard M.
Thesis Committee:
  • Murray, Richard M. (chair)
  • Marsden, Jerrold E.
  • Burdick, Joel Wakeman
  • Low, Steven H.
Defense Date:5 December 2005
Record Number:CaltechETD:etd-06262006-171822
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-06262006-171822
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2735
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:29 Jun 2006
Last Modified:26 Dec 2012 02:53

Thesis Files

[img]
Preview
PDF (thesis_master.pdf) - Final Version
See Usage Policy.

660Kb

Repository Staff Only: item control page