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
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|
|Defense Date:||21 May 2007|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||23 May 2007|
|Last Modified:||26 Dec 2012 02:45|
- Final Version
Restricted to Caltech community only
See Usage Policy.
Repository Staff Only: item control page