DOC PREVIEW
UCF EEL 6788 - The Contract Net Protocol

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IEEE TRANSACTIONS ON COMPUTERS, VOL. C-29, NO. 12, DECEMBER 1980 1104 The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver REID G. SMITH, MEMBER, IEEE Abstract — The contract net protocol has been developed to specify problem-solving communication and control for nodes in a distributed problem solver. Task distribution is affected by a negotiation process, a discussion carried on between nodes with tasks to be executed and nodes that may be able to execute those tasks. We present the specification of the protocol and demonstrate its use in the solution of a problem in distributed sensing. The utility of negotiation as an interaction mechanism is discussed. It can be used to achieve different goals, such as distributing control and data to avoid bottlenecks and enabling a finer degree of control in making resource allocation and focus decisions than is possible with traditional mechanisms. Index Terms—Artificial Intelligence (AI), connection, cooperation, distributed problem solving, focus, high-level protocols, negotiation, resource allocation, task-sharing. I. INTRODUCTION IS lTRIBUTED problem solving is the cooperative so- ution of problems by a decentralized and loosely cou-pled collection of knowledge-sources (KS's) (procedures, sets of production rules, etc.), located in a number of distinct pro-cessor nodes. The KS's cooperate in the sense that no one of them has sufficient information to solve the entire problem; mutual sharing of information is necessary to allow the group, as a whole, to produce an answer. By decentralized we mean that both control and data are logically and often geographi-cally distributed; there is neither global control nor global data storage. Loosely coupled means that individual KS's spend most of their time in computation rather than communication. Such problem solvers offer the promise of speed, reliability, extensibility, and the potential for increased tolerance to un-certain data and knowledge, as well as the ability to handle applications with a natural spatial distribution. There has been much recent interest in this type of problem solving in the Artificial Intelligence (AI) community. Its use has been con- Manuscript received March 4, 1980; revised May 9, 1980. This work was supported in part by the Advanced Research Projects Agency under Contract MDA 903-77-C-0322, the National Science Foundation under Contract MCS 77-02712, and the National Institutes of Health under Grant RR-00785 on the SUMEX-AIM Computer Facility at Stanford University, Stanford, CA and by the Defence Research Establishment Atlantic of the Department of National Defence, Research and Development Branch, Dartmouth, N.S. Canada. The author is with the Defence Research Establishment Atlantic, Dart-mouth, N.S., Canada. sidered in such applications as traffic-light control [5], dis-tributed sensing [7], and heuristic search [10]. In this paper, we present the contract net protocol, a high-level protocol for communication among the nodes in a dis-tributed problem solver. It facilitates distributed control of cooperative task execution (which we call task-sharing [9]) with efficient internode communication. The role of a high-level protocol in a network such as the ARPANET has been discussed in previous papers (see, for example [11]). Traditional communication protocols form a low-level base for problem-solving communication. They en-able reliable and efficient transmission of bit streams between nodes, but do not consider the semantics of the information being passed. A high-level protocol assigns interpretations to the bit streams. It offers a structure that assists the system designer in deciding what the nodes should say to each other, rather than how to say it. We are not primarily concerned with the physical archi-tecture of the problem solver. It is assumed to be a network of loosely coupled, asynchronous nodes. Each node contains a number of distinct KS's. The nodes are interconnected so that each node can communicate with every other node by sending messages. No memory is shared by the nodes. We also assume the existence of a low-level communication protocol to support reliable and efficient communication of bit streams between nodes. A functional model of a node is shown in Appendix A. II. CONNECTION AND CONTRACT NEGOTIATION The key issue to be resolved in task-sharing is how tasks are to be distributed among the processor nodes. There must be a means whereby nodes with tasks to be executed can find the most appropriate idle nodes to execute those tasks. We call this the connection problem. Solving the connection problem is crucial to high performance in a distributed problem solver. It has two aspects: 1) resource allocation and 2) focus. Ef-fective resource allocation is achieved by balancing the com-putational load among the nodes. It is essential if the maximum speedup possible from applying multiple nodes to a single overall problem is to be obtained. Focus is achieved by effective selection of tasks for allocation to nodes and by effective selection of KS's for execution of tasks. It is essential for problems that do not have well-definedD © 1980 Canadian Crown CopyrightSMITH: CONTRACT NET PROTOCOL: COMMUNICATION AND CONTROL 1105 algorithms for their solutions (i.e., problems of the type most often considered in AI). For such problems, many tasks are typically generated during the search for solutions; and the execution of many of these tasks will not lead to a solution. In addition, the most appropriate KS to invoke for the execution of any given task generally cannot be identified a priori. The combination of many tasks and many applicable KS's can lead to a combinatorial explosion. A problem solver must therefore maintain focus to achieve high performance in practical ap-plications. The connection problem can also be viewed from the per-spective of an idle node. It must find another node with an appropriate task that is available for execution. In our ap-proach, both nodes with tasks to be executed and nodes ready to execute tasks proceed simultaneously. They engage each other in discussions that resemble contract negotiation to solve the connection problem. It is this process that is the basis for the contract net protocol. For our purposes, negotiation has four important compo-nents: 1) it is a local process that does not involve centralized control, 2) there is a two-way exchange of


View Full Document

UCF EEL 6788 - The Contract Net Protocol

Documents in this Course
Load more
Download The Contract Net Protocol
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view The Contract Net Protocol and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Contract Net Protocol 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?