A Caltech Library Service

Local-to-Global in Multi-Agent Systems


Pilotto, Concetta (2007) Local-to-Global in Multi-Agent Systems. Master's thesis, California Institute of Technology. doi:10.7907/JY2K-6194.


The thesis presents performance analysis and simulation results for algorithms that compute global functions out of local interactions on multi-agent systems. We focus on optimization problems; this is because many problems can be formulated in terms of designing algorithms which optimize some global function subject to local constraints.

We model the environment as an adversary of the system. The environment is able to attack the system, modifying the system in arbitrary ways: some agents and/or communication links can be disabled.

Computations proceed by opportunistically employing the resources available at each point, progressing rapidly when more resources are available and slowing down when resources become unavailable.

We investigate and compare two techniques. In the first one, each sub-system (which we call group) behaves like a centralized system, i.e., it solves its specific optimization sub-problem by applying a central algorithm. We investigate this technique, called self-similarity, showing examples where it works and where it fails, and carry out performance analysis on some problems. Then, we introduce a second technique which is completely decentralized but synchronous: agents simultaneously makes a local update to their current estimates of some true parameter using the estimates of their adjacents. We prove the correctness of this technique on some specific problems by applying tools from distributed systems (variant functions) and control theory (equilibrium points of a dynamical system).

Item Type:Thesis (Master's thesis)
Subject Keywords:distributed systems; multi-agent systems
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Chandy, K. Mani
Thesis Committee:
  • Unknown, Unknown
Defense Date:21 May 2007
Record Number:CaltechETD:etd-05232007-084106
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1983
Deposited By: Imported from ETD-db
Deposited On:23 May 2007
Last Modified:05 Feb 2020 20:41

Thesis Files

PDF (thesis.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page