Department of Computer Science
University of Northern Iowa
Appears in Pattern Languages of Program Design 3,
edited by Robert Martin, Dirk Riehle, and Frank Buschmann,
Addison Wesley, 1997, pages 67-78.
Brokered Resources, Implicit Invocation
The Sponsor-Selector pattern can be used to provide a mechanism for selecting the best resource for a task from a set of resources that changes dynamically. It allows a software system to integrate new resources, and new knowledge about resources, at run-time in a way that is transparent to users of the resources. This pattern is based on the idea of separating three kinds of responsibilities: knowing when a resource is useful, selecting among resources, and using a resource.
Consider a software system engaged in the task of medical diagnosis. The system has at its disposal a set of sub-systems capable of performing particular diagnostic sub-tasks. The task/sub-task structure may look something like this:
Figure 1: A Task Structure for Diagnosis
At each point during a diagnostic session, the system faces the question: Which sub-task should be performed next? This is the question of problem-solving control. Early systems of this kind performed their sub-tasks sequentially, or in some other prescribed order, but such "hard coded" control produced unsatis-factory results. Often, the data provided by previous actions indicated the need to break out of the prescribed sequence -- say, to gather more specific data while doing causal reasoning about a hypothesis -- in order to arrive at the best diagnosis in a timely manner.
Ideally, one would think of the diagnostic system as having an agent responsible for performing each task in this hierarchy. At run-time, the system would like to select the most appropriate sub-task agent to invoke, based on the context information available at that point. This involves determining which of the sub-systems is likely to make the most progress toward the goal of arriving at a useful diagnosis.
Situations like this arise in many domains: An operating system may want to select the best process scheduling algorithm based on the current state of the system. A central web server may want to balance access load across a family of web servers based on their current performance capabilities. A communication network may want to select the best route for a message based on the current state of the network and its components. In all of these examples, a system needs the ability to select a resource dynamically from a set of resources whose attri-butes may be changing at run-time.
You are building a system in which the set of resources used to perform some task, or the system's knowledge about those resources, can change, either statically or dynamically.
Sometimes, a class has a number of other classes (resources) with which it can collaborate, but it cannot know until run-time which of these resources it will need in a specific situation. Furthermore, the set of potential collaborators may change over time, either statically by programmer modification or dynamically during system execution. At run time, the class would like to select the "best" collaborator based on the context information available at that point.
However, designing such a control mechanism introduces new problems. One solution to this problem is to encode a resource selection mechanism directly into the system. Such a solution leads to two kinds of difficulties: If the programmer adds a new resource to the system, the system's control knowledge must be modified to make it accessible. And if a new resource is added to the system dynamically at run-time -- say, through some form of machine learning -- the system is unable to use the resource, because its control knowledge makes no reference to the new resource.
A second solution is to separate the selection mechanism into a separate class that specializes in control decision-making, using the Blackboard pattern. This solution makes the system immune to modification in the face of new resources. But this still confounds knowledge about resource applicability with knowledge about resource preference, making the new "selection" class prone to the same difficulties when new resources are added to the system.
Any solution to this problem should bring the following forces into equilibrium:
Introduce sponsor and selector components to achieve a higher degree of decoupling between the system and the resources it uses. Each resource has a sponsor whose responsibility is to recommend when it can be used. The selector takes these recommendations as input and decides which resource should be used.
In the course of execution, whenever the system needs a resource to proceed, it sends a request to the selector in charge of the corresponding resource set. The selector then broadcasts the request to all of the sponsors in the set. Each sponsor evaluates the applicability of its resource and sends a rating back as its answer. The selector then uses these ratings, along with other preference knowledge and context information, to select the "best" resource for the client in the current context.
A new resource can be added to the system either statically or dynamically by building a sponsor for it and registering the new sponsor with the appropriate selector. In many situations, the creator of the resource will also need to register specific preferences that relate to the new resource with the selector as well.
The key to the Sponsor-Selector pattern is the separation of three fundamentally different responsibilities: recommending a resource, selecting among resources, and using a resource.
The Sponsor-Selector pattern comprises three kinds of components: a selector, a set of sponsors, and a set of resources. Together, these components provide a set of services to some client.
Figure 2: The Structure of Sponsor-Selector
A resource is any one of a set of objects that has specific functionality in some larger context.
Each sponsor contains knowledge of when its resource is appropriate for use. This knowledge makes reference only to local features of the environments in which the resource is useful. If possible, a sponsor should make no reference to any resource other than its own.
The selector embodies knowledge of which resource to prefer in particular kinds of situation. This knowledge can express preferences among groups of resources and can make reference to global features of the context, such as issues of run-time efficiency and correctness. The selector sends requests to the set of sponsors and receives a set of ratings in return. It then uses these ratings to select a resource for use in the current context.
The client is a system that uses the resources to perform some part of its task. It sends requests to the selector when it needs a resource and invokes the resource that is returned by the selector.
In our example, the client is the diagnostic system. The resources are the sub-systems that perform parts of the diagnostic system's task, for example, the hypothesis builder and the causal reasoner. Each sub-system has an associated sponsor that indicates whether or not the diagnostic system should invoke the sub-system in a given situation. The task selector uses its knowledge to select the sub-system to invoke next, based on the ratings returned by the sponsors and information about the diagnostic system's current context.
Figure 3: The Sponsor-Selector Pattern Applied to the Diagnostic Example
A Sponsor-Selector system operates in the following manner.
Figure 4: The Dynamic Behavior of the Sponsor-Selector Pattern
The client reaches a point in its activity at which it needs a resource in order to proceed, so it asks the selector for a resource. The selector broadcasts a request to all sponsors, each of which rates its resource and returns a rating for the resource. The selector uses these ratings to select the most appropriate resource and then asks the corresponding sponsor for its resource. The selector then returns this resource to the client. The client uses the selected resource in the desired way.
In our example, the diagnostic system completes some activity and must begin working on a new sub-task. It asks the task selector to select the next sub-task to work on. The task selector broadcasts a request to all sub-task sponsors, which rate their sub-tasks for applicability in the current context. The task selector then uses these ratings to select the next sub-task and asks the corresponding sponsor for its resource. The selector returns this sub-task to the diagnostic system, which begins working on the selected sub-task
Several common patterns can be used to implement the components of the Sponsor-Selector pattern. Sponsors may be implemented using the Proxy pattern, since they stand in the place of resources during the selection process. The selector may be implemented using the Broker pattern, which coordinates communication between the client and its decoupled resources. Finally, if the resources themselves are methods to be invoked, they can be implemented using the Strategy pattern.
Regardless of how the components of the pattern are built, three main implementation decisions must be made:
Two other implementation issues should be considered:
The use of the Sponsor-Selector pattern resolves the forces at play in our diagnostic system example. By creating sponsors for each sub-task and encoding the selection mechanism in the task selector, changes to the task structure of the system are localized.
Suppose that we wished add a new sub-task, say hypothesis identification, to the system. This sub-task might involve selecting a new hypothesis to consider while building the system's diagnosis. A programmer could make this addition to the system by:
No other changes to the selector or to the client would be necessary.
However, since all change is localized around the new sub-task, the addition could also be done both by the system itself at run-time. During execution, the system could use some form of machine learning to discover and encode new diagnostic knowledge. When a new sub-task is discovered, all information that is needed to add the resource to the system (what it is and when it is useful) is created as a part of the learning process. The final step of registering the new sponsor with the selector involves little or no change to the structure of the selector itself.
A number of interesting variations of Sponsor-Selector are possible:
Figure 5: A Hierarchy of Sponsor-Selector Modules
A hierarchy of Sponsor-Selector patterns provides a means for organizing complex resource sets, such as the many tasks, sub-tasks, and methods of a large system, in a way that promotes system modifiability in the face of change.
The first documented use of Sponsor-Selector was in DSPL (Brown and Chandrasekaran, 1986), which used the pattern in a mechanism for selecting design plans in a system that designed air cylinders for aircraft. The mechanism was incorporated into a shell for building knowledge-based systems that do "routine design," in which much or all of the design task is accomplished through the use of pre-enumerated design and redesign plans.
TIPS (Punch and Chandrasekaran, 1993) generalizes Sponsor-Selector into a mechanism for making dynamic control decisions about sub-tasks. Punch has applied TIPS in the construction of a medical diagnostic expert system.
FAULTY-II (Benjamins 1993) goes further by using a Sponsor-Selector pattern as the basis of an application framework for dynamically selecting a method for performing each sub-task in explicitly represented task structures.
IPCA (Decker et al., 1994) uses Sponsor-Selector as the basis for control plan selection and execution in a system that controls microwave composite material processing in a soft real-time environment.
Goel and his colleagues (1994) have used Sponsor-Selector for dynamic method selection in navigational planning for mobile robots. Experiments in this domain confirm that Sponsor-Selector is a good design solution in situations where the client application is learning new control knowledge. As the planner acquires domain knowledge, Sponsor-Selector enables the agent to incorporate the new knowledge dynamically into its problem solving and to select the method that is indicated by that knowledge. The planner has been embodied in a physical robot that demonstrates the effectiveness of its plans.
Landauer and Bellman (1995) have proposed a new technique for developing, integrating, and managing complex software systems based on an idea very similar to that of the Sponsor-Selector pattern. Their technique uses two types of component, wrappings and managers. Wrappings are qualitative information about a system component: how to use the component, when and why to use it, and in what combinations they can be used. Managers are algorithms that select and combine components based on the information in their wrappings. This technique extends Sponsor-Selector to apply to all components of a system at all times.
Many of the consequences that follow from using Strategy also follow from using Sponsor-Selector. Sponsor-Selector offers the following benefits:
Sponsor-Selector also imposes some drawbacks:
One way to address these potential couplings is to use the Observer pattern as a mechanism for allowing selectors and sponsors to view external context information without encoding context into these components.
As described above, Sponsor-Selector may incorporate many of the features of the Broker, Proxy, and Strategy patterns. Mementos, Observers, Singletons, and Flyweights may be used to address some of the issues that arise when implementing Sponsor-Selector.
Sponsor-Selector is similar to the Blackboard pattern in its decoupling of control from the resources that comprise a system. But Sponsor-Selector also adds an extra degree of flexibility by further decoupling knowledge of when a knowledge source is useful (the sponsor) from the knowledge source itself (resource). This flexibility can be realized by adding an extra layer to the system's architecture.
Client-Dispatcher-Server also resembles Sponsor-Selector in its decoupling of the client from the resources that serve it. But Sponsor-Selector further prescribes that knowledge of when a knowledge source is useful be decoupled from the knowledge of which resource to use at any point in time. The Client-Dispatcher-Server pattern makes no commitment in this respect. Both Sponsor-Selector and Client-Dispatcher-Server can be viewed as architectural forms of implicit invocation (Notkin et al., 1993), an idea that can be applied even at the level of general-purpose programming languages.
When taken to the level of wrappings (Landauer and Bellman, 1995), Sponsor-Selector can be viewed as a mechanism for implementing the Reflection pattern. Sponsor-Selector provides a means by which a system can reflect about its own sub-tasks and methods and select resources when they are most useful for achieving the system's goals. Furthermore, Sponsor-Selector allows the system to fully integrate new resources at run-time while retaining its ability to reflect about them.
An earlier version of this pattern appeared at PloP'96. Shepherd Chris Landauer first suggested the relationship between Sponsor-Selector and the ideas of wrapping and implicit invocation. I thank the members of PloP'96 Working Group 4 for their valuable criticisms and suggestions for improvement. Frank Buschmann, Eric Hughes, and Peter Sommerlad were especially helpful, providing thorough written comments on my paper. Finally, I thank Bobby Woolf, whose thoughtful comments helped me to think about how readers outside the domain of knowledge-based systems might interpret my pattern.