Below, we briefly present a summary of the Negotiated Retrieval Algorithm. Interested reader is referred to [Nagendra Prasad, Lesser, &Lander1996][Nagendra Prasad, Lesser, &Lander1995] for a more formal treatment and empirical studies.
Negotiated Retrieval is viewed as a distributed constraint optimization problem where each agent has a set of subcase consistency constraints in addition to the local case base. These constraints arise in a number of ways:
A case can be viewed as a set of feature-value pairs. The set of constraints that an agent has may be defined on both "local" and "non-local" features. Local features of an agent are those features that the agent uses to represent its local subcases. Non-local features are those features that some other agent uses to represent its local cases. Thus, a constraint can be viewed as a relationship between subcases of one or more case bases and is enforced through interrelationships between features of these subcases.
A case has a number of associated attributes that involve measures of certain characteristics of a case and are functions of the feature values of a case. Examples of attributes include reliability, quality, uncertainty and cost. In addition to being acceptable to all agents, it is desirable that a case be optimized along the attribute set. These requirements lead to organization of an agent's constraints as soft constraints and hard constraints where the former set represents solution preferences and the later set represents those constraints that are relaxed only as a result of explicit recognition by the agents that the set is too constrained to lead to a mutually acceptable solution. Relaxing a soft constraint may only involve penalties in terms of loss of optimality in the desirable attributes. For example, relaxing a soft constraint may lead to less robust solutions. Softness of a constraint represents its degree of flexibility. On the other hand, hard constraints are generally not relaxed except with an explicit understanding that the resulting responses satisfy the query specifications only partially or are consistent with only a subset of the agents.
A partial case is a partially evolved response to a query. A partial case is obtained by composing the subcases from one or more agents but it is not yet acceptable to all agents (perhaps because it needs more subcases or because other agents have not checked it against their consistency constraints). Projection of a partial case on to a set of features is the set of feature-values pairs in the partial case for that set of features.
The agents execute the Negotiated Retrieval Algorithm (NRA) as follows:
If an agent received feedback from other agents about previous violations, it first assimilates it (details of the assimilation process are provided later). Some of the agents, using the relevant portions of the user query and the presently available information on the problem-solving state (including previously tried solutions, conflicts they caused and feedback in the form of advice on violated constraints from other agents), retrieve the seed subcases around which the rest of the case evolves. Other agents have too poor a local view to perform retrieval without additional help and hence wait to extend partially assembled cases. If a seed agent fails to retrieve a case, it can relax some local constraints until it finds a case or gives up at certain point. In general, a locally retrieved subcase is re-instantiated in the present problem context during this phase. Re-instantiation could also involve adaptation of the retrieved subcase to the new context.
Agents try to "merge" the local subcases to form larger partial
cases. It involves checking for consistency and interactions among the
sub-cases retrieved by different agents. In the situation where the
agents are trying to physically represent the overall episode at a
single central repository, the agents can easily obtain the relevant
information for consistency checking by looking at the other agents'
sub-cases in the central repository. However, integration need not
necessarily lead to a combination of the sub-cases at a single
physical location. In this situation, the agents have to exchange
projections of partial cases. For example, agent 
wanting a
consistency check on one of its partial cases by 
has to send to
, a projection of that
partial case with respect to the relevant
features of the constraints at agent . Projection information
alone is sufficient for Agent to check for the consistency of
that partial case with respect to its constraints (more details can be
found in [Nagendra Prasad, Lesser,
&Lander1996]). If constraints are not violated then
the subcases are considered "merged" due to their mutual
consistency. Those agents who could not retrieve subcases due to
insufficient information in Phase I, try to extend these partial cases
by adding their subcases. An agent intending to extend a partial case
obtains an appropriate projection of that partial case to serve as an
anchor for the local subcase retrieval.
If any violations are detected during a merge or an extend operation due to poor or infeasible values on local or non-local features, go to Phase III; else exit.
Each agent categorizes its violated local constraints into pre-enumerated classes of violations and uses a set of conflict resolution strategies associated with each of these categories to generate a set of advice as feedback to itself and the other agents involved in the partial case that led to the conflicts. The set of advice could range from domain independent strategies to highly domain specific ones[Nagendra Prasad, Lesser, &Lander1996]:
Upon generating feedback, goto Phase I.
Assimilation of feedback advice from other agents enhances an agent's view of the non-local requirements. An agent assimilating feedback can indulge in a process as complex as the generation of feedback. It may involve relaxing a constraint or adding a new constraint to the local set of constraints. Assimilation may be context-sensitive, leading to constraints that are applicable only in specific contexts or to specific types of partial cases at the local agent. In addition, the assimilation process may also involve transformations where an agent uses the feedback from other agents to generate its own local constraints rather than directly incorporate the feedback.
The Negotiated Retrieval Algorithm is an asynchronous parallel distributed constraint optimization search to obtain a good overall episode assembled from case pieces. The asynchronous nature of the search arises from the fact that an agent could be in any phase of the NRA for a given case evolution at a given time. More than one partial case could be evolving simultaneously and an agent could be in different phases of Negotiated Retrieval for different partial cases at any given time. The NRA algorithm is very general and a system may go through only some or all of these phases to achieve coherent retrieval of good overall cases.
Another feature of Negotiated Retrieval Algorithm is its ability to work with heterogeneous agents. While we cast NRA as constraint optimization search, it is not essential that the agents represent these constraints in any particular form - they could be procedural or declarative and in multiple forms. Internally, the agents could be using disparate knowledge organizations or problem solving control organizations. Agent detects constraint violations based on projections that basically represent information about the features that this agent as well as some other agents know about. The only requirement is the ability of an agent to translate a projection or feedback into its local language or from its local language to the language of another agent. These types of translation mechanisms are commonly called "wrappers"[Genesereth, , &Ketchpel1994] and are used to enable a set of heterogeneous or stand alone systems to function as a multi-agent system.