|
Project: Scalable Decentralized Directory Services
|
Introduction:
Multi-Agent Systems researchers are interested in studying the
interactions between large numbers of autonomous, possibly mobile
agents. Such systems are a potential means of dealing with the
complexity that arises in large distributed computer systems. In
principle each agent can be put in charge of a small independent
task. Larger joint tasks are then achieved by allowing agents to
decide among themselves upon a division of labor. Systems are
able to adapt to changing conditions such as network failures,
addition or removal of agents or new user requirements, through
the self organizing capabilities of the agents.
The above description is, of course, the ideal case, current agent
systems are far more limited. One of the challenges faced is the
question of how agents seeking partners with particular
capabilities can find each other. Traditionally this function is
fulfilled by directory servers. These act like the yellow pages
phone book; agents publish an advertisement for the capabilities
they provide and as clients can query the directory for a list of
others agents providing a particular function.
Directories are however essentially centralized components that
provide a "global" view. Meanwhile, ideally, multi-agent systems
are autonomous decentralized systems, where each agent needs only
local interactions to function. Many of the potential advantages
of multi-agent systems stem from this principle of
decentralization; the ability to scale to accommodate large
numbers of agents, the ability to adapt easily by only changing a
part of the system, the ability to support a large variety of
agents requiring unpredictable information to make decisions. Thus
the problem of how directory services can be replaced with
decentralized mechanisms belongs to one of the fundamental
questions of multi-agent systems research.
Approach:
In this project we address this problem by considering extremely
simple, abstract agents. We study how a grouping, or clustering,
function among these agents can assist in randomized local search.
Without a directory to turn to agents can do little more than
query their neighbors in the hope that what they are seeking is in
the neighborhood. Should they fail to find it, they need a way of
expanding their outlook. We take the view that decentralization
is best maintained by keeping the size of an agents 'neighborhood'
constant, but that agents with an uninteresting initial
neighborhood should be perfectly willing to exchange it for
another. Further, while cooperating with an unknown neighbor may
be an odd behavior, a small amount of cooperation between groups
of 'friends' can more easily be argued to be advantageous.
Challenges:
In our current research we are studying the ability of these
simple agents to do decentralized, capability based, clustering.
Our vision is that if we can cluster agents while they remain
distributed over a network, we can use the cluster structure to
enable searches, removing the need for a directory server. We
have found that the agents do exhibit a clustering tendency,
meaning that we can achieve the traditional centralized clustering
task in a decentralized peer-to-peer manner. We are however faced
with the core difficulty of clustering in general: how to define
where the borders of clusters should be placed. Thus much of our
current work focuses on methods in which agents can learn cluster
properties such as size, area, and density.
