Coordination Methods for Open Distributed Systems
This project aims to develop methods to decentrally coordinating
the actions of agents by using market-based models of
interaction. We are interested in how to construct complex plans
and resource allocations, and applying the results in a "band-width
market". The new idea is to use derivatives to express more complex
resource demands while maintaining the volatility of the resources in
the market.
Contents
Global vs. decentralized
planning
Complex technical systems need to be able to coordinate their behavior
by themselves when they get interconnected. Integrating information
systems often greatly increases the usefulness of the combined systems,
but when two systems initially designed to work alone get interconnected,
the combined behavior may become undesirable. For instance, connecting
two computer systems that handle resources at a company may generate dead-locks
and failure to allocate resources properly. A way to design systems
in a way that the behave desirably or "gracefully" even when they are interconnected
is needed. Designing systems for decentralized coordination is one
way to tackle some of the potential problems that may arise.
This project aims to develop methods to decentrally coordinating the
actions of agents. Coordination is broadly the process of
deciding when a task should be performed and which resources that should
be used. Coordination is necessary in domains where resources are shared
between agents, when the resources are limited and when using a resource
can inhibit another agent from fulfilling its goals.
Factories, communication networks and company work flow are all examples
of domains where coordination is necessary.
Coordination can be performed centrally by a global planner or
in a decentralized fashion. Global planning is the process
of collecting information from all agents involved and using that to design
a (unique) time plan for each agent. The agent may not deviate from
this plan during execution. Decentralized planning means that the
decisions of which actions to take are delegated to the agents. It
almost always also implies that each agent makes its decision based on
only a subset of the information used by the global planner. This
has the advantage of allowing the agents to make faster decision and to
make partial changes in their plans if their goals or environment changes.
An algorithm that only uses a subset of the total information may be
unable to find the optimal solution of a coordination problem, something
which may or may not be acceptable depending on the domain. Therefore,
many decentralized algorithms are search heuristics approaching good solutions
rather than a computation delivering the optimal global behavior.
Decentralized coordination is therefore useful for problems where no global
planner can deliver a solution within reasonable time.
Another (and perhaps more interesting) area where decentralized coordination
may prove useful is in domains where the first priority of a participating
agent is to maximize its own performance rather than the global
performance. Competing organizations/companies as well as individuals
can be represented by such agents. For companies, a decentralized
coordination framework will allow sharing and trading of resources as long
as it is beneficent for the individual companies. Individuals will program
their personal assistants to prioritize the interest of its client user
over that of other agents (such as advertisers or sales agents).
We call the domain open when it intends to support the existence
of self-interested agents. Domains that do not assume that agents
are self-interested will have to control and limit which agents that may
interact with the system, i.e. the system will in generally be closed.
Market-oriented coordination
The project will in particular investigate market-oriented approaches to
coordination. A key idea for this approach is to represent the systems
and resources that need to be coordinated by agents that broker their resources
on an exchange. Other agents are responsible for obtaining the resources
needed to fulfill the goals of the users. Coordination of the resources
amounts to exchanging resources and finding market prices such that all
agents are satisfied. Note that satisfied means that the agent has
no intention to trade, which can be the case if the resources are too expensive.
Compared to other research in this area where agents can negotiate and
commit, a market based approach has "simpler" interactions (only bidding),
and can therefore be expected to be faster. But if we only allow
bidding on the resources, agents have no way to construct more complex
plans without large risks or inefficiency. Therefore, we will introduce
derivatives into the market, and design agents that generate plans by bidding
on options and/or futures. This may allow agents to produce complex
plans, indirectly taking into use the capabilities of several other agents.
In a market (without external events), resources are iteratively interchanged
towards a more stable state of allocation. When events occur, such
as adding new resources to the system or failure of participating components,
the prices of the resources change as a result of the event. This
will cause the agents to take on trading again, but considering the new
state of affairs. In this sense, a market based system can be considered
to be self-coordinating and adaptive.
Project motivation and objective
Many large distributed systems of today are very vulnerable to change and
misuse. The fact that they are not open systems and that it is a
single organization that controls what is added to the system has somewhat
limited the potential danger. For example, the telephone network
would be vulnerable if anyone could connect their own switch to it, not
to speak of adding their own software. One is often even reluctant
to introduce improvements or even bug fixes, as it is difficult to foresee
the consequences of changes to a system in which all components are critically
dependent on each other .
The result of the inability to design complex systems is a comparatively
low level of interaction among systems. Even highly computerized organizations
often use separate systems with no or little inter-connection. But
this is under a strong pressure of change from business re-engineering
processes that necessitate an a potentially very profitable integration
of systems and information.
Coordinating the work of several independently working individuals can
enable several new services. For example, software agent technology
can create digital markets (market spaces) where companies can establish
business contacts and help them to put together their middle-ware products
into complete products. The simple interactions of offering and buying
products can be transformed into a complex system of product refinement,
without the need of a large organization directing production towards the
goal. Not all systems support such a transformation process.
This study will provide insight into ways of designing systems that support
integration.
Our goal is to develop methods and mechanisms that enable us to construct
robust open systems of highly interacting parts.
We will investigate how to design systems with decentralized coordination
by creating the necessary tools and communication protocols to allow systems
to delegate tasks and coordinate their actions and resource usage.
We will investigate how vulnerable the proposed protocols are to manipulation
and misbehavior, both deliberate and unintended. Computer models
and simulations will be made, as well as the integration of the results
into existing agent-frameworks currently under development at SICS.
Self-coordinating systems are robust in the sense that they can reconfigure
and adapt to a dynamic environment. The robustness should be on two levels:
-
Robustness against failure - A set of highly integrated systems has components
that rely on several of the other subsystems to work and may require a
lot of reconfiguration if some of its parts break down. The complex
reorganization that has to be performed in case of partial failure will
be achieved by the system itself if a decentralized coordination mechanism
is used to coordinate the components.
-
Robustness against misuse - A system can potentially be misused if it is
possible for anyone to connect any new software or system to the system.
To minimize the risk for misuse, we wish to avoid coordination protocols
that demand that the components have to believe that the other components
cannot manipulate them. Instead, agents should only cooperate with
other agents in those cases it is beneficent for themselves.
Research topics
Market oriented programming
The market oriented programming paradigm [1, 3,
13] deals with allocating resources among agents [10].
Consumers of shared resources in a system are modeled as agents that buy,
sell, produce or consume resources.
Agent-oriented coordination of tasks is often done in a decentralized
fashion, where agents distribute tasks among themselves through negotiations,
rather than by using a central planner. Agents use facilitators to
locate possible agents that they can cooperate with, and requests the other
agent to perform the task at hand. Market-oriented programming further
reduces the negotiation process to a Contract Net like protocol [12]
of bidding and awards.
Topics
The topics we start out to investigate are among others
-
planning by using derivatives
-
higher level behavior as coalition formation
-
market behavior as communication channels
-
bids that express negotiation
-
applications:
-
network bandwidth market for allocation of resources
-
consumer power distribution market for coordinating deals for users with
different preferences
-
factory scheduling for the creation of complex plans
Our research hypothesis is that market-oriented programming will generally
be a lot faster negotiation mechanism than the more complex conversations,
but that the framework for coordination will have to support both kinds
of coordination.
The most interesting question to investigate to see to what extent it
is possible to express more complex behavior as commitments and delegations
in terms of actions using financial instruments. For instance, can
an agent delegate its intention to achieve a task to another agent by buying
a certain portfolio of futures or options? This would have two large
advantages, namely the speed of interaction and to translate utility to
economic terms.
Speed would increase since the agent would simply announce intentions
to buy or sell financial instruments. It would not have to locate
potential interested agents itself, nor would anyone have to figure out
a way to partition the tasks among several agents.
In previous work we were concerned with the possibility to manipulate
agents into performing actions that were potentially harmful for their
clients. By translating the utility of actions into economic terms,
an agent will have a better opportunity to compute the real benefit and
risk that is associated with its decision.
A network market
In the first year we will create a simulation environment for routing
of telephone and Internet traffic in a computer network
environment. The problem specification comes from a related
cooperation project at SICS with Telia. The Swedish telephone
backbone consists today of about ten thousand routers that route the
traffic between towns. The configuration (topology) of the
network is constrained by several factors that depend on the
particular routers that exist, such as maximum through-put, number of
virtual channels, etc. The goal of the network market is to
create a routing behavior that is flexible, can reorganize traffic in
case of partial failure, incorporate new routers and even to allow
other telecom providers to connect their networks to the system.
The network market consists initially of a commodities exchange where
agents announce bandwidth that they have bought from the routers.
Other agents represent consumers with certain needs for bandwidth.
Consumer agents will buy traffic at the market for prices that determined
by the current traffic and congestion levels in the network.
We will extend this model to a market of distributed commodity
exchanges. It is desirable to have several exchanges, since it
reduces the bottle neck that a single exchange would become.
This however generates a whole new set of problems. Agents have
to decide on which markets they should announce their bids, if they
should announce the same resource on several markets, etc. Live
loops may occur in the bidding, which has to be avoided.
Planning
"Options trading is the trading in rights and obligations. You pay for
the rights and you get paid for the obligations.'' -- OM
With complex financial instruments such as options or futures, it may
be possible to create behavior similar to coalition formation or shared
plans. Compared to other research in this area where agents can negotiate
and commit, a market based approach has "simpler" interactions (only bidding),
and can therefore be expected to be faster. But if we only allow
bidding on the resources, agents have no way to construct more complex
plans without large risks or inefficiency. Without the ability to
ask others for help, agents have to buy resources speculatively, not knowing
if they will eventually obtain all the required resources.
A market with derivatives may allow agents to produce complex plans,
indirectly taking into use the capabilities of several other agents.
An agent that needs a particular resource in the future may need to plan
that it has the resource. Agents may reduce the risk they take when
they plan, by buying an option to obtain the resource at a later time.
The interesting thing about this is that it reduces coordination through
negotiation to a risk decision problem, which may be faster to compute.
Related work
Some related international
research
For a fuller account of related research, please refer to the bibliographic
study Decentralized coordination of open distributed systems [7].
Software agent systems
Software agent systems consist of computer programs that autonomously contact
different service providers, trying to obtain a goal that matches
a request from its client. One popular example is a travel agent
that puts together a complete itinerary for a long trip, matching plain
schedules with buses, taxis etc. and orders the tickets. The
client just specifies when and where she want to go, and the agent knows
about personal preferences such as window/aisle seat etc., from earlier
missions.
Research with great commercial interest is being carried out in the
software agent area. The majority of this is in the United States,
but also Japan and many other European countries show considerable interest.
For a survey of current activities in this area, see http://www.sics.se/isl/abc/survey.html.
Coordination
The research area of coordination as applied to general complex systems
is relatively new, although some roots (organization theory, market economy
dynamics) can be traced back several decades. It has gained a lot
of scientific interest, especially due to the explosive growth of interconnected
computer systems.
Cooperative behavior as an emergent property of complex systems is a
very active area also in distributed artificial intelligence. For
example, the Santa Fe Institute in New Mexico is devoted to the study of
complex systems, including medicine, genetics, A-Life and more.
Economic approaches
Research in economic approaches for organizing complex systems is made
by [7] and [6] and others. Non-manipulable
communication protocols for collaboration formation are investigated by
[9] and [2]. The use of ecological
models to investigate computational aspects of complex systems is promoted
by [3] and [5].
One system that uses market oriented programming techniques is the
TRACONET system by Tuomas Sandholm at the University of Michigan [11].
TRACONET is a system of transportation agents that collaborate to find
an efficient way to transport goods, sharing the work among them.
Sandholm has investigated several of the issues of security in market oriented
programming, such as safe exchange of goods, etc.
The market that we will investigate under the first year will partly
resemble the transportation economy of Sandholm or that of Wellman [13,
14], but our focus will be on plan generation and on
how to express more complex relationships between the agents than has been
possible in the earlier work. For instance how to design a bid such
that it resembles an offer for a set of other agents to take part in a
plan.
References
- [1] Scott H. Clearwater. Market-based Control, A Paradigm
for Distributed Resource Allocation. World Scientific, Palo Alto, CA, 1996.
- [2] E. Ephrati, Gliad Zlotkin, and J.S. Rosenschein.
Meet your destiny: A non-manipulable meeting scheduler. In Conference on
Computer Supported Cooperative Work, North Carolina, October 1994.
http://ccs.mit.edu/1994wp.html.
- [3] B.A. Huberman. The Ecology of Computation. North-Holland,
1988.
- [4] Thomas W. Malone and Kevin Crowston. The interdiciplinary
study of coordination. ACM Computing Surveys, 26(1):87--119, March 1994.
http://www.acm.org/pubs/articles/journals/surveys/1994-26-1/p87-malone/p87-malone.pdf
- [5] M.S. Miller and K.E. Drexler. Comparative ecology:
A computational perspective. In B.A. Huberman, editor, The Ecology of Computation.
North-Holland, 1988.
http://www.agorics.com/agorpapers.html
- [6] M.S. Miller and K.E. Drexler. Market and computation:
Agoric open systems. In B.A. Huberman, editor, The Ecology of Computation,
chapter 7. North-Holland, 1988.
http://www.agorics.com/agorpapers.html
- [7] Lars Rasmusson. Decentralized coordination for open
distributed systems. SICS Report, October 1997.
- [8] Lars Rasmusson and Sverker Janson. Simulated social
control for secure internet commerce. Proceedings of the New Security Paradigms
Workshop '96, 1996.
http://www.sics.se/~lra/exjobb/simsoccontr/simsoccontr.html
- [9] J. S. Rosenschein and G. Zlotkin. Rules of Encounter:
Desiging Conventions for Automated Negotiation among Computers. MIT
Press, 1994.
- [10] Tuomas Sandholm. An implementation of the contract
net protocol based on marginal cost calculations. In AAAI-93, pages 256--262,
1995.
ftp://ftp.cs.umass.edu/pub/lesser/sandholm-aaai93-traconet.ps
- [11] Tuomas Sandholm and V. Lessner. Equilibrium analysis
of the possibilities of unenforced exchange in multiagent systems. In 14th
International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal,
Canada, 1995.
- [12] Reid G. Smith. The contract net protocol: High-level
communication and control in a distributed problem solver. IEEE Transactions
on Computers, C-29(12):1104--1113, December 1980.
- [13] Michael P. Wellman. A market-oriented programming
environment and its application to distributed multicommodity flow problems.
Journal of Artificial Intelligence Research, 1, August 1993.
http://ic-www.arc.nasa.gov/ic/jair-www/volume1/wellman93a.ps
- [14] Michael P. Wellman. A computational market model
for distributed configuration design. In Proceedings of the Twelfth National
Conference on Artificial Intelligence, Seattle, WA, August 1994. AAAI.
ftp://ftp.eecs.umich.edu/people/wellman/aaai94ext.ps.Z
Maintained by Lars Rasmusson, 1998-04-29
Page Formatted for Printing