 |
 |
|
Research Fact Sheet
Xplore: negotiation based coordination.
|
|
Xplore is a negotiation oriented
lightweight platform aimed at coordinating distributed autonomous
software components.
Context
Negotiation is a pervasive aspect of everyday life, and it is not surprising
that many approaches have been proposed to use computer software to support
some forms of negotiation processes in various collaborative applications,
e.g. electronic trading, meeting scheduling and service matching. More
generic forms of negotiation also exist in service discovery mechanisms,
advanced transaction models, quality of service selection etc. While most of
these proposals make sense in the context of the applications for which they
have been designed, they are hardly transportable across applications, and
across architectural layers within an application. In other words, there is
a strong need for defining a truely generic model of negotiation and a set
of related tools that any distributed application could rely on at multiple
levels. Xplore [1] provides a lightweight coordination
platform, proposing negotiation as a new concept to enrich the set of
traditional coordination facilities offered by component based systems,
providing flexible support for applications with unrestricted types of
multi-party, multi-attribute negotiations.
Overview of Xplore
A negotiation in Xplore is modeled as a collaborative process among
autonomous decision-makers, possibly distributed and with different goals
and resources, towards the definition of an agreement as to a set of actions
to be executed by each of them. Such a process involves two types of
components: the participants and a coordinator that tries to make the
participants reach the agreement. The same component can be a participant
in one negotiation and a coordinator in another, so the notions of
coordinator/participant are always relative to one specific negotiation
(just as the traditional notions of client/server are relative to a
communication session).
Xplore provides a rich representation of the state of a negotiation,
well beyond the traditional state-transition graphs. Furthermore, this
representation is entirely decoupled from the dynamics of the negotiation
processes that may use it, and hence avoids to rely on any specific
``rule of the game'' as to how a negotiation should proceed.
The negotiation process itself consists of a structured set of decisions
expressed by the participants as contributions towards the agreement. The
components in a negotiation (both coordinators and participants) exchange
information about the issues of the negotiation. To support heterogeneity,
the infrastructure makes no assumption as to how the components store these
information and in what format. The only assumption is that each issue of
the negotiation can be described by its properties.
The participants are provided with the ability of exploring concurrent
alternatives for reaching their goal and with appropriate contextual
information for making informed decisions. Once an agreement is reached,
the corresponding actions are transactionally executed by the participants.
Applications
Applications of Xplore have essentially been investigated in the domain of
E-Commerce and B2B process support. In particular, we are using Xplore as
the negotiation infrastructure for Virtual Alliances, such as an
alliance of printshops which negotiate among them in order to outsource or
insource some of their print jobs, possibly split into multiple slots
[2].
Negotiation model
- Negotiators and negotiation agreements.
In Xplore, a negotiator (e.g. a printshop) is modeled as a set of
participants, where a participant is an encapsulated piece of
software and each visible action it can perform is externally described by
an ``invocation''. For example, in the case of a printshop alliance, a
printshop negotiator can be defined as a set of participants offering both
services for outsourcing and for insourcing print jobs. A negotiation
agreement among negotiators is expressed as a combination of the kind of
services that the negotiators may provide in order to reach a consensus.
For example, in the case of the printshops, the negotiation agreement will
be expressed as a combination of outsourcing and insourcing services that
the printshops are willing to provide in order to find an agreement for
performing a print job. The negotiation process allows to refine the
definition of such services for the given print job, e.g. price and deadline.
- Negotiation state.
The state of a negotiation is represented as a graph that logs the
decisions made by the negotiators and their dependencies. A negotiation
graph may contain two types of nodes: white nodes, representing
negotiation contexts, and black nodes, representing
decision points with multiple alternatives. Each white node is
decorated with specific information about the state of the negotiation at
that node. For example, in the case of the printshops, a white node can
contain information on a proposal made to an outsourcer printshop from a
candidate insourcer printshop to perform a job at a given cost and for a
given deadline. Figure 1 shows an example of
negotiation graph. In particular, nodes
1 and
2 represent two alternative
negotiation contexts, each with a different proposal in terms of cost and
deadline for performing a print job. The option offered by the context in
node 2 is cheaper than the one
offered in node 1, but with a shorter
deadline.
Figure 1: An example of an Xplore negotiation graph.
- Negotiation Process.
A negotiation process is modeled as the collaborative construction of a
negotiation graph among the participants. Each participant has its own
partial copy of the graph, showing the appropriate view of the state of
the negotiation according to its declared interests. For example, the
state of a negotiation among a printshop, who wants to outsource a print
job, and a group of insourcers, who would like to insource that job, is
represented by a global negotiation graph. However, the outsourcer
printshop manages a partial copy of the negotiation graph which shows the
current state of its proposal for outsourcing the job, while the insourcing
printshops manage the partial copies of the graph showing the current state
of their proposals for insourcing the job.
A participant expresses negotiation decisions manipulating its copy of the
graph, performing on it a number of operations invoking the verbs of the
Xplore protocol, which are appropriately propagated to the other copies.
The Connect verb allows to dynamically involve a new participant in a
negotiation. The Open and Assert verbs allow each participant
to build the negotiation graph, by creating and populating context nodes
with information about the negotiation state at these nodes. The
Request verb avoids livelock situations by allowing participants to
express their information needs in order to proceed in the negotiation.
Typically, the participants make requests on the aspects they would like the
negotiation to be based on (e.g. the price of a print job). The Ready
and the Quit verbs allow a participant to declare respectively that
it is ``ready to sign'' in the state of a given negotiation context, or, on
the contrary, that it wishes to leave that branch of the negotiation at that
state (but it may pursue the negotiation in other branches).
The Xplore protocol allows the synchronisation of the different partial
copies of a negotiation graph. As a result of this synchronisation process,
a participant is only partially informed of the other participants actions
on the negotiation graph. Thus, the participants do not communicate directly,
but the communication is achieved through the collaborative construction of
the negotiation graph.
References
- 1
-
J-M. Andreoli, and S. Castellani.
"Towards a Flexible Middleware Negotiation Facility for Distributed
Components". In Proc. of "e-negotiations" (DEXA'01), Munich,
Germany, 2001.
- 2
-
J-M. Andreoli, and S. Castellani.
"A Software Infrastructure for Negotiation within Inter-Organisational
Alliances". In Proc. of "Agent Mediated Electronic Commerce"
(AAMAS'01), Bologna, Italy, 2002.
Contacts
For more information on the Xplore research project please contact:
Jean-Marc Andreoli or Stefania Castellani
e-mail: Jean-Marc.Andreoli@xrce.xerox.com, Stefania.Castellani@xrce.xerox.com
address: 6, chemin de Maupertuis, F-38240 Meylan
tel: +33 (0)4 76 61 50 50
fax: +33 (0)4 76 61 50 99
www: http://www.xrce.xerox.com