``Essential Issues in Distributed Computational Systems''
Prof. William P. Birmingham
The University of Michigan
Electrical Engineering and Computer Science Department
Artificial Intelligence Laboratory
Ann Arbor, MI 48109
E-mail: wpb@eecs.umich.edu
URL: http://ai.eecs.umich.edu/people/wpb/home.html

Complex computational systems are manifested in many applications, such as engineering design (also known as concurrent engineering), digital libraries, and the simulation of various natural and man-made phenomena. Two common characteristics of these systems are the following: they are cast as distributed systems, composed of many elements that coordinate their computation to achieve shared (and perhaps individual) goals; and, they are open-ended in their requirements, implying that they evolve in terms of computation and tasks they perform, and the support that they give to users.

We have developed two complex computational systems for large-scale engineering-design and digital-library applications. These systems are distributed, as they are composed of hundreds of computational elements; for these applications the elements are software agents. These agents make various types of decisions using private (non-shared) knowledge and preferences. They coordinate their actions using a variety of mechanisms, some based on microeconomic methods, and some based on constraint-satisfaction and decision-theoretic methods.

An important property of the systems we have built is that they have decentralized control. We define informally such a system as a one where there is no centralized decision maker, database, or any other computational element upon which the system critically depends. A common example of a decentralized system is the World Wide Web, where there is essentially no single controlling mechanism. We believe that decentralized control is essential to developing complex computational systems.

In view of the characterization of complex computational systems given earlier, we see some of the advantages of constructing decentralized systems as the following: decentralization implies a very modular software architecture that is easy to scale; incentive mechanisms can be designed to entice third parties to add, or remove, capabilities to the system, making the system more adaptive to changing requirements; control over proprietary resources can be maintained by individual organizations; and, it can be easier to model complex scientific problems, and then design and engineer complex computational systems as collections of smaller elements. Thus, we believe there are many advantages to a strongly decentralized view of computation.

From the perspective of the systems we have developed, some of the requirements for a decentralized system are the following:

• Coordination: an agent of the type we have developed is usually incapable of solving by itself the types of problems a user puts forth to the system. Thus, an agent must enlist the services of other agents. For example, in our digital library, many agents are involved in responding to a document query: one agent interfaces the user to the library, another plans a search strategy, another searches for documents in various document collections, yet another may reformulate the query, and so forth. This type of interaction requires coordination among the agents, both in terms of the types of computation they jointly perform, but also in terms of the incentive structure that motivates the agents to work together.
• Common Communication Structures: coordination requires that agents in our systems send messages with intent. This, in turn, requires that the agents have a common message structure that includes syntax and semantics. In addition, various rules of the game (e.g., all agents are truthful) must be clear to all agents.
• Ontologies: A shared ontological commitment among agents is essential. Not only is this necessary for communication and coordination, but the ontology can be used for other tasks. For example, in the digital library, we use formal ontologies for both "advertising" services for agents, but also for search and query reformulation. Thus, formal ontologies with concomitant inference abilities have many benefits for decentralized systems.