CaltechTHESIS
  A Caltech Library Service

Local-to-global in multi-agent systems

Citation

Pilotto, Concetta (2007) Local-to-global in multi-agent systems. Master's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-05232007-084106

Abstract

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:Restricted to Caltech community only
Research Advisor(s):
  • Chandy, K. Mani
Thesis Committee:
  • Unknown, Unknown
Defense Date:21 May 2007
Record Number:CaltechETD:etd-05232007-084106
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-05232007-084106
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1983
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:23 May 2007
Last Modified:26 Dec 2012 02:45

Thesis Files

[img] PDF (thesis.pdf) - Final Version
Restricted to Caltech community only
See Usage Policy.

1679Kb

Repository Staff Only: item control page