\documentclass[12pt]{article}

\usepackage{url}
\usepackage{epsfig}
\usepackage{moreverb}
\usepackage{xspace}

\newcommand {\twoK}{\emph{2K}\xspace}
\newcommand {\dTAO}{\emph{dynamicTAO}\xspace}
\setlength{\textheight}{53pc} 
\setlength{\textwidth}{39pc}
\setlength{\topmargin}{-10mm} 
\setlength{\oddsidemargin}{0mm}
\newcommand{\class}[1]{\texttt{#1}}
\newcommand{\method}[1]{\texttt{#1}}

\bibliographystyle{alpha}

\begin{document}
\title{Automatic Configuration of Component-Based Distributed Systems\\
       {\large\emph{(Preliminary Examination Statement)}}}
\author{Fabio Kon\\ {\em f-kon@cs.uiuc.edu} \\ \\
        Advisor: Prof. Roy H. Campbell\\ \\
        Department of Computer Science\\
	University of Illinois at Urbana-Champaign
}

\maketitle


%abstract
%The Problem
%The Proposed Solution
%Completed work
%Proposed work
%Related Work
%Conclusions


\begin{abstract}
- problem

- solution

- completed work

- research plan
\end{abstract}

\newpage

\tableofcontents

\newpage

\section{The Problem}

As computer systems are applied to more and more aspects of personal and
professional life, the quantity and complexity of software systems have
increased considerably. At the same time, the diversity in hardware
architectures remains large and is likely to grow with the deployment of
embedded systems, PDAs, and portable computing devices. All these
architectures will coexist with personal computers, workstations, computing
servers, and supercomputers. It is imperative that the scientific and industrial
communities develop techniques to support seamless integration of highly
heterogeneous environments. Clearly, the construction of these new software
systems and applications in an easy and reliable way can only be achieved
through the composition of modular hardware and software.

Component technology has appeared as a powerful tool to confront this
challenge. Recently developed component architectures support the construction
of sophisticated systems by assembling together a collection of off-the-shelf
software components with the help of visual tools or programmatic interfaces.
However, there is still very little support for managing the interactions
between components. Components are created by different programmers, often
working in different groups with different methodologies. It is hard to create
robust and efficient systems if the dynamic dependencies between components
are not well understood.

\subsection{Fault Tolerance}

It is very common to find cases, in both legacy and component-based systems,
in which a module fails to accomplish its goal because an unspecified
dependency is not properly resolved. The description of two real-life examples
of this problem follows.
\begin{enumerate}
\item It happens when a program such as Netscape Navigator 4.06 is requested
to print a web page while running on a Solaris 2.6 machine in which no printers are
configured. Neither the system nor the application give any error message to
the user. They simply do not print the page. If the printer is not available,
the printing option should not be offered to the user in the first place.

\item When a member of our research group purchased a new DELL Inspiron 7000
laptop computer, he realized that the maximum video resolution supported by
the video driver was $600 \times 480$. Moments before returning the computer
to the vendor, he installed the network driver to test the network
connection. To his surprise, after the network driver was installed, the video 
driver started to work at higher resolutions, up to $1024 \times 768$. The
nature of the unspecified dependency between the video and the network driver
remains a mistery.
\end{enumerate}

Sometimes, the graceful failure of one module is not properly detected by
other modules leading to system failure. A real-life example follows.

\begin{itemize}
\item pcl-cvs 1.05 is a window-based front-end to the CVS version control
system that runs within GNUS Emacs. When pcl-cvs is used to update a local
copy of a source code tree with respect to the master CVS repository, it
issues a call to the command-line version of the CVS client. If the
command-line client generates an error message that is not understood by the
window-based front-end, the whole update process is aborted. In many cases,
all but an irrelevant file are properly updated. But, since pcl-cvs is not
prepared to deal with such cases, it fails completely.
\end{itemize}

\subsection{System Administration}

Current systems are continuously being updated and modified. For
example, system administrators working on UNIX or Windows NT environments must
be aware of security announcements on a daily basis and be prepared to update
the operating system kernel with security patches. Users demand new versions
of applications such as web browsers, text editors, software development
tools, and the like. Often, building and installing a new package requires
that a series of other tools (e.g., make, cc, ld, pearl, find) be updated.

Users of workstations and personal computers are also not free from the burden
of system or account maintenance. In environments like MS-Windows, the
installation of some applications is partially automated by ``wizard''
interfaces which directs the user through the installation process. However,
it is common to face situations in which the installation cannot complete or
in which it completes but the software package does not run properly because
some of its (unspecified) requirements are not met. In other cases, after
installing a new version of a system component or a new tool, applications
that used to work before the update, stop functioning.  It is typical that
applications on MS-Windows cannot be cleanly uninstalled. Often, even after
executing special uninstall procedures, ``junk'' libraries and files are still 
left in the system.

\subsection{Operating System Architecture}

Modern computers vary enormously in capacity, functionality, and architecture.
Existing computational devices range from very simple embedded systems and
PDAs, commodity notebooks and PCs, to powerful workstations and supercomputers.
Users on different kinds of computers usually require different kinds of
applications and system services.

Existing operating systems are not adaptable to this variety in
architectures and to different service requirements. In general, the OS
carries a large set of dependent components that are often not needed by any
of its users. These leads to an inneficient use of resources and to
performance degradation. In addition, the process of reconfiguring the
OS requires either recompilation or, at least, rebooting the host machine.

In the commercial world, companies address these issues by creating static,
specialized operating systems. MS-Windows, for example, comes in different
flavors: NT Server, NT Workstation, 98, CE. They are large, static systems
tailored to different kinds of machines and users. The migration from one
version of the system to the other is abrupt and requires the reinstallation
of the whole system.

Microkernels such as L4 \cite{l4} and dynamically extensible systems such as
SPIN \cite{bershad:spin} enable the configuration of OS services at
runtime. Now, the questions is no longer \emph{how} to configure the system but
\emph{when} and \emph{in which manner}. Defining exactly which software
modules must be installed in an OS environment is crucial for its performance
and usability.

On one hand, the system may be kept small and only a few modules (e.g. the key
device drivers and user-level servers) are loaded. This minimalist configuration
may be robust and efficient but will probably not address all the needs of its
users in different contexts.

On another hand, one may configure the system to include everything that might
be required including different kinds of service daemons, drivers, profilers,
maintenance packages, etc. This is the path that is most commonly adopted in
the world of personal computing. What happens is that too many software
packages are executed wasting CPU, memory, and network resources, thus
degrading the performance of the applications that really matter.

\subsection{The Heart of the Problem}

The problem behind all these difficulties is the lack of a model for
representing the dependencies among system and application components and
mechanisms for managing these dependencies.

In the next section, I argue that operating system and middleware environments
must provide support for representing the dependencies among software
components in a explicit way. This representation can then be manipulated with
the objective of implementing software components that are able to configure
themselves and to adapt to ever-changing dynamic environments. I will show how 
the reification of dependencies can be used to solve the problems described in 
this section.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Proposed Solution}

As discussed in the previous section, the technology of computer systems
continues to advance rapidly and the rate of change is not likely to decrease
in the next decades.  A significant part of these advances have the goal of
making computer systems easier to use, to manage, and to
maintain. Paradoxically, the rate of change is so large that it has
turned the development and maintenance of computer systems into a Herculean
task.

The research on object-oriented technology and its intensive use by the
industry has led to the development of \emph{component-oriented programming}
as a way of fighting against the nine-headed hydra of software development.
Rather than being an alternative to object-orientation, component technology
extends the initial concept of objects.  It stresses the desire for
independent pieces of software that can be reused and combined in different
ways to implement different software systems.

Another use of component technology is illustrated by the \twoK project
\cite{twoK:wroops98}. In this project, we are working on the development
of adaptable systems that will dynamically load, unload, and rearrange their
components in order to accommodate themselves to changing environments.

Three major component architectures have been developed in the last
years. JavaBeans \cite{JavaBeans97}, ActiveX Controls
\cite{ActiveX:candib,ActiveX:denning} and the CORBA Component
Model\footnote{The OMG CORBA Component Model is still in its design phase.}
\cite{corba:component} intend to provide an infrastructure to support the
construction of complex applications from off-the-shelf components.

However, existing component architectures lack support to analyze and exploit the
dependencies among components. The \twoK project seeks to modify the way computer
systems support component-based software to accommodate dynamic changes in
rapidly evolving environments. By maintaining an explicit representation of
the interactions between system and application components, the infrastructure
can recognize the need for reconfigurations. In addition, it can know how to
carry out this reconfiguration without compromising system stability,
performance, and reliability.

The goal of this research is to apply the knowledge about component
requirements and dependencies to permit the automatic configuration of software
systems with little or no intervention from system administrators or
users. This thesis will focus on developing formal
models and software tools for reifying the interactions between
components. With these tools, we will produce an infrastructure
for automatic configuration of distributed component-based systems.

The infrastructure for automatic configuration will provide the means for
guaranteeing that new configurations can be achieved with an affordable cost,
with the best quality of service, and in a reliable way. Also, the system will
be able to handle exceptional behavior gracefully taking care of faulty
components and connectivity problems.

This thesis will offer an important software infrastructure which has been
neglected by existing object and component architectures.  It has a great
potential impact on the reliability, robustness, flexibility, and automatic
adaptability of next generation distributed systems.

\subsection{Inter-Component Dependence}


I now describe the model for representing dependencies and discuss how it can
be used to solve the problems mentioned in the previous sections.  The
solutions here described can be implemented in any of the above mentioned
component architectures.

%The goal of my research is to provide support for representing the
%dependencies among software components in a explicit way. With that support,
%I will develop mechanisms that utilize this representation to perform
%automatic (re)configuration of software components in dynamic environments.


\subsubsection*{What You Need Is What You Get}

%solution to OS architecture: minimalistic architecture

In contrast to existing systems where a large number
  of non-utilized modules are carried along with the basic system installation,
  the \twoK philosophy is based upon a ``what you need is what you get'' 
  (WYNIWYG) model.  
The system configures itself automatically and loads
  the minimum set of components required for executing the user applications 
  in the most efficient way. 
These components can be downloaded from the network and only
  a small subset of system services are needed to bootstrap a node, leading to 
  the construction of ``network-computers''. 

This thesis will help implementing this WYNIWYG model by supporting the
reification of inter-component dependence.  System and application components
will contain an explicit representation of the requirements that need to be
fulfilled before their execution.  An internet browser, for example, would
specify that it depends upon components implementing an X-Window system, a
local file service, the TCP/IP protocol, and the Java virtual machine version
1.0.2 or later.

Inter-component dependence characterizes exactly the requirements
 for a service. 
Thus, the system can download and execute only the minimal
 set of components that are required to provide the requested services.
Moreover, dependencies can be satisfied in alternate ways, leading the way
 to adaptation. 

\subsection{Prerequisites versus Runtime dependencies}

The architecture I propose manages two distinct kinds of
dependencies:

\begin{enumerate}
\item Requirements for loading an inert component into the runtime system
(called \emph{prerequisites}).
\item \emph{Runtime dependencies} among loaded components in a running
system.
\end{enumerate}

As long as the system knows exactly what the requirements are for
installing and running a software component, the installation and
configuration of new components can be automated. As a byproduct of this
knowledge, component performance can be improved by analyzing the dynamic
state of system resources, analyzing the characteristics of each component,
and by configuring them in the most efficient way.

In addition, if the system knows what the dynamic dependencies among running
components are, it can (1) better handle exceptional behavior that could
potentially trouble component operation, and (2) support dynamic
reconfigurations of large systems by replacing individual components
on-the-fly.

I will analyze alternative ways to represent component 
prerequisites and consider how they can be implemented in different
environments. I will also develop a theoretical model and a pratical
implementation of an infrastructure for representing dynamic dependencies.


\subsubsection*{Are Them Really Different Entities?}

As a matter of fact, one could argue that prerequisites and runtime
dependencies are two forms of the same entity. Prerequisites usually are
expressed as dependencies on ``persistent'' hardware and software components
while runtime dependencies refer to dynamic, possibly volatile, components. In
paticular, by freezing runtime dependencies and freezing component
state, one can later reload a component by using the frozen runtime
dependencies as the prerequisites for melting the component.

However, in order to make the model as clear as possible, I am going to treat
prerequisites and runtime dependencies as separate entities. Prerequisites
usually refer to hardware resources, QoS requirements, and software
services. Runtime dependencies usually refer to loaded software
components. Thus, I believe that the separation of concepts is justifiable. In
the future, after the basic problems are solved, I may consider to unify these
concepts in order to build a simpler and more generic model.



\subsection{Representing Prerequisites}

The prerequisites for a particular inert component must specify any
special requirement for properly loading, configuring, and executing that
component. There are three different kinds of information that can be
contained in a list of prerequisites.

\begin{enumerate}
\item The nature of the hardware resources it needs.
\item The capacity of the hardware resources it needs.
\item The software services (i.e., components) it requires.
\end{enumerate}

The first two items may be used primarily by the operating system Resource
Management Service to determine where, how, and when to execute the
component. QoS-aware operating systems can use these data to enable proper
admission control and resource reservation.

The last item is the one which determines in which kind of software
environment the component will execute. A more complex model model can be
designed by splitting the third item in two items specifying the nature and
capacity of the required software services. I decided to limit the model to
the present form to make it easier to understand and deal with. This might be
reconsidered as the research advances.

Table \ref{tab:prerequisites} contain examples of information that can
be present in prerequisite specifications.

\begin{table}
\begin{center}
\begin{tabular}{|c|l|}
\hline
               & processor family: x86, Sparc, PowerPC \\
Nature of      & processor type: 486DX2, Sparc20, PPC601/80 \\
Hardware       & network family: ethernet, fast ethernet, ATM \\
               & device type: MPEG decoder, CD-ROM writer \\
\hline
Capacity of    & CPU throughput $\geq$ 100 Mhz (or 100 Mips) \\
Hardware       & Network bandwidth  $\geq$ 5 Mbps \\
\hline
               & DNS name of a service \\
SW Components  & reference to a interface description \\
               & URL of a component \\
\hline
\end{tabular}
\end{center}
\caption{Information in prerequisite specifications}
\label{tab:prerequisites} %the label must always follow the caption
\end{table}

As part of this thesis research I will investigate alternatives for representing 
prerequisites. Another student in our group is studying the representation of
QoS-related prerequisites in the context of the \twoK operating system. The
implementation of a powerful language for representing different classes of
prerequisites is out of the scope of this thesis. I will simply implement a
limited prototype so that the whole architecture can be exercised. In any
case, the framework will be developed in a way that enables the utilization of 
different kinds of prerequisite representations.

\subsection{Representing Dynamic Runtime Dependence}

A major goal of my model is to facilitate installation and configuration of
software components in order to ease the work of system administrators and
users. However, at the same time, I must avoid complicating the work of
component developers. The model should not require programmers to follow too strict
rules and to write too much extra code to conform to it. Clearly,
these two goals conflict with each other. Thus, a careful
analysis of the problem is needed to solve this tradeoff in the best way.

In my model, each component is managed by a component configurator which is
responsible for storing the dependencies between a certain component and
other system components.
Depending on the way it is implemented, a component configurator may be able
to manage components running on a single address space, on different
address spaces and processes or even running on different machines.
Figure \ref{fig:dependencies} depicts the dependencies reified by the
component configurator.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode \epsfig{file=dependencies.eps,width=6.5in}
    \caption{Reification of component dependence.}
    \label{fig:dependencies}
  \end{center}
\end{figure}

Each component $C$ has a set of \emph{hooks} to which other components can be
attached. These are the components on which $C$ depends and they are called
\emph{hooked components}. There might be components that depend on $C$, these
are called \emph{clients}.  In general, each time one defines that a component
$C_1$ depends on another component $C_2$, two actions are performed:

\begin{enumerate}
\item $C_1$ attaches $C_2$ to one of its hooks and 
\item $C_2$ adds $C_1$ to its list of clients.
\end{enumerate}

Consider the example mentioned in the introduction in which a web browser
specifies, in its list of prerequisites, that it requires a TCP/IP service, a
window manager, a local file service, and a JVM. Its component configurator should
maintain a hook for each of these services. When the browser is loaded, the
system must verify whether the services are available in the local
environment. If they are not available, it must create new instances of them. 
In any case, references to the services are stored in the browser
configurator hooks and may be later retrieved and updated if necessary.

\subsubsection{The \class{ComponentConfigurator} class}

The reification is accomplished by assigning an instance of the
\class{ComponentConfigurator} class to each component.
The simplified declaration of \class{ComponentConfigurator} in pseudo-C++
follows.

\begin{center}
\begin{boxedverbatim}
class ComponentConfigurator {
 public:
  virtual ComponentConfigurator (Object *implementation);
  virtual ~ComponentConfigurator ();

  virtual int hook (const char *hookName, ComponentConfigurator *cc);
  virtual int unhook (const char *hookName);
  virtual int registerClient (ComponentConfigurator *client, 
                              const char *hookNameInClient = NULL);
  virtual int unregisterClient (ComponentConfigurator *client);

  virtual int eventOnHookedComponent 
                            (ComponentConfigurator *hookedComponent,
                             Event e);
  virtual int eventOnClient (ComponentConfigurator *client,
                             Event e);

  virtual char *name ();
  virtual char *info ();
  virtual char *listHooks ();
  virtual ComponentConfigurator *getHookedComponent
                                              (const char *hookName);
  virtual DependencySpecification *listHookedComponents ();
  virtual DependencySpecification *listClients ();

  virtual Object *implementation ();
}
\end{boxedverbatim}
\end{center}

The class constructor receives a pointer to the component implementation as
a parameter. A pointer to the component implementation can be later obtained
through the \method{implementation()} method. Figure \ref{fig:method-calls}
shows a schematic representation of some of the \class{ComponentConfigurator}
method calls.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode \epsfig{file=methodCalls.eps,width=6.5in}
    \caption{Methods for managing dependencies.}
    \label{fig:method-calls}
  \end{center}
\end{figure}

The \method{hook()} method is used to specify that this component depends upon
another component and the \method{unhook()} breaks this dependence. 

The \method{registerClient()} and \method{unregisterClient()} methods are
similar to \method{hook()} and \method{unhook()} but they specify that other
components (its clients) depend upon this component. The optional parameter 
\texttt{hookNameInClient} specifies the client hook to which this
component is attached.

\method{eventOnHookedComponent()} announces that a component which is attached
to this component has generated an event. The \class{ComponentConfigurator()}
class can be subclassed to implement different behaviors when events are
reported. Examples of common events are the destruction of a hooked component,
the reconfiguration of a hooked component, or the replacement of the
implementation of a hooked component. Users can create
application-specific events and use the framework to distribute them.

\method{eventOnClient()} is similar to the previous method but it announces
that a client has generated an event. This can be used, for example, to trigger
reconfigurations in a component to adapt to new conditions in its clients.
My reference implementations will define a basic set of events including
\class{DELETED}, \class{FAILED}, \class{RECONFIGURED}, \class{REPLACED}, 
\class{MIGRATED}, etc. Applications can extend this set by specifying their 
own events.

\method{name()} returns a pointer to a string containing the name of the
component and \method{info()} returns a pointer to a string containing a
description of the component. Specific \method{info()} implementations can
return different kinds of information like a list of configuration options
accepted by the component, or a URL for its documentation and source code.

\method{listHooks()} returns a string containing a list of hooks in this
component.  Different items in the string are separated by a
CR/LF pair, i.e., by the string ``$\backslash$r$\backslash$n''.

\method{getHookedComponent()} returns a pointer to the configurator of the
component that is attached to a particular hook.
\method{listHookedComponents()} returns a pointer to a null-terminated
sequence of \class{DependencySpecification}s. A 
\class{DependencySpecification} is a structure defined as
\begin{center}
\begin{boxedverbatim}
struct DependencySpecification {
 const char *hookName;
 ComponentConfigurator *component;
};
\end{boxedverbatim}
\end{center}
Later, if necessary, the definition of \class{DependencySpecification} can be
extended to support the attachment of multiple components to a single hook.

\method{listClients()} returns a pointer to a null-terminated sequence of
\class{DependencySpecification}s corresponding to the components that depend
on this component (its clients) and the name of the hooks (in the client's
ComponentConfigurator) to which this component is attached.


\subsubsection{Automating Fault-tolerance and Exception Handling}
\label{sec:automating}

As discussed above, reified inter-component dependence can help the
automation of the configuration process. By scanning the list of
prerequisites, the operating system or middleware can make sure that all
requirements for the execution of a particular component are met before it is
initiated. This can avoid a large number of problems that are common in
existing applications in which the lack of a particular component is only
detected after the application is running.

The dynamic dependence information, in its turn, enables the reconfiguration
of components that are already running. It provides important
information for implementing fault-tolerance and smooth exception handling in
environments of either local or distributed components.

As an example, consider the deletion of a component containing an instance of
the \class{ComponentConfigurator} class. 
Different policies for dealing 
with component deletion can be adopted. In general, when a component $C$ is
destroyed, an announcement must be made to components that depend on $C$ and
to components on which $C$ depends.
%In general, the fact that a component
%is being destroyed must be announced to components that depend on this one and
%to the components on which this component depends. 
The following piece of pseudo-C++ code illustrates this process with a
conservative implementation of the \class{ComponentConfigurator} destructor.

\begin{center}
\begin{boxedverbatim}
ComponentConfigurator::~ComponentConfigurator ()
{
  for (c in hookedComponents)
    {
        c.configurator->unregisterClient (this);
    }

  for (c in clients)
    {
        c.configurator->eventOnHookedComponent (this, DELETION);
    }

  // delete list of hooks and hooked_components 
  // delete list of clients
  // release resources
  // delete component implementation
}// ~ComponentConfigurator ()
\end{boxedverbatim}
\end{center}

Implementations of this destructor can be specialized to adjust its behavior
to different component types and to meet special requirements. Also, different
component types must implement methods such as
\method{eventOnHookedComponent()} in proper ways to take care of the
different kinds of dependencies. In a extreme case, deleting a component will
cause all components that depend on it to be deleted. In another extreme case,
these other components will only be notified and nothing else will change. In
most of the cases, one expects that the components will try to reconfigure
themselves in order to deal with the loss of one of their dependencies.

\subsubsection{But It Is Not that Easy}

The problem with this implementation is that the complete destruction of the
component only takes place if all the method calls to hooked components and to
clients return. If any of these calls block, the component is not
deleted. This problem is particularly important if some of the clients decide
to initiate their own destruction as a result of the call to
\method{eventOnHookedComponent()} and a long chain of calls is established.

A na\"\i ve solution to this problem is to execute the method calls
asynchronously (for example, by creating new threads to perform the calls) and
deleting the component implementation without waiting for the calls to
return. This solution would incur in the additional cost of creating new
threads and could lead to dangerous situations as a C++ component could try to
call a method on another component after the latter is destroyed.

Thus, it seems that one is trapped between a safe, conservative solution that
might block indefinitely and a liberal but unsafe solution that may crash the
whole system by executing invalid code.
I propose two solutions that lie somewhere between these two, they are as
safe as the conservative one but are less subject to blocking.

\subsubsection{Solution One: \texttt{valid} Flag}

The first idea is to implement a very light-weight version of the
\method{eventOnHookedComponent()} method that simply registers
the fact that the dependence is being deleted and returns without ever
blocking.

A flag, \texttt{valid}, is added to the \class{ComponentConfigurator} class and
to the components.  When the destructor for a component $C_{server}$ is called, the
first thing it does is to assign \texttt{False} to its \texttt{valid} flags and
then release all the hardware and software resources it holds. Sample code
follows.

\begin{center}
\begin{boxedverbatim}
ComponentConfigurator::~ComponentConfigurator()
{
  this->valid = False;
  this->implementation()->valid = False;
  // release resources

  for (c in hookedComponents) {
   c.configurator->unregisterClient (this);
  }
  // delete list of hooks and hookedComponents 

  for (c in clients) {
   c.configurator->
      eventOnHookedComponent (this, DELETED);
  }
  // wait until list of clients becomes empty
  // delete list of clients
  // delete component implementation
}// ~ComponentConfigurator ()

inline int 
ComponentConfigurator::eventOnHookedComponent 
         (ComponentConfigurator *cc, Event e)
{
  if (e == DELETED) {
   this->deletionEventList.add (cc);
   return;
  }
  else ...
}
\end{boxedverbatim}
\end{center}

Once $C_{server}$ is marked as invalid, any subsequent call, by a component
$C_{client}$, to one of the methods in $C_{server}$ throws an exception to indicate
that the component is no longer functioning. Possibly, methods executing in
other threads may also fail -- due to the resources being released -- throwing
an exception.  Upon catching these exceptions or realizing that its
\method{eventOnHookedComponent()} method was called, 
$C_{client}$ should call the method \method{unregisterClient()} on $C_{server}$ and
reconfigure itself to deal with the loss of $C_{server}$.

$C_{server}$'s destructor must wait until the list of clients becomes empty
and then return finishing the component destruction process.

The advantage of this process is that the component being destroyed can
immediately release all the resources it is holding. Even if the complete
destruction of the component takes a long time or blocks indefinitely, all the 
resources are released and there is no risk of the component being called
after its destruction.

\subsubsection{Solution Two: Leases}

The previous solution still does not present a robust solution to the case in
which one of the clients fails to respond to the component being
destroyed. This can be addressed by assigning an expiration time to the validity
of the reified dependencies between components. This mechanism is known as
\emph{leases} \cite{leases} and is also used in other contexts like the SODA
distributed file system \cite{soda95} and JINI \cite{JINI:whitePaper98}.

After a lease is expired, a component may assume that the dependency no longer 
exists and complete its destruction process.
In this case, a component that relies on a particular dependency must always
verify if the lease for this dependency is still valid. Alternatively, a timer
can be set for each leased dependency so that the system can preempt a
component to inform that one of its leases has expired.

The problem with this solution is the extra complexity that it adds to the
system. It complicates component development and leads to space and time
overheads.

\subsection{Final Solution: Reflective Method Invocations and CORBA}

All of the discussed solutions requires strict collaboration from the
component developer to conform to the proposed models.  It is important that
all the communication between the components be done through controlled
interfaces.  In order to avoid a proliferation of programming errors related to
the dependence reification, it would be necessary to develop special
languages, compilers, and runtime systems to guarantee the safety of component
execution.

A cleaner solution is to use existing reflective languages and environments
\cite{ACMCS::Cointe1996}. Iguana \cite{dsg-97} and OpenC++ \cite{openC++}, 
for example, are extensions to C++ that reify several features of this
language, allowing dynamic modification of their implementations.  Guaran\'a
\cite{guarana98} extends the Java Virtual Machine to support flexible runtime
reflection using the standard Java programming language.  In these systems,
it would be possible to instrument method invocation to take care of
dependence maintenance.

However, a major goal of this research is not to limit the implementation to a
particular programming language but to develop a generic model that could be
utilized in a large number of heterogeneous environments. These requirements
can only be met by using an architecture like CORBA.

CORBA permits the integration of different programming languages in
heterogeneous environments. In addition, CORBA's (remote) method invocation
mechanism can be decoupled from the base language method call. Thus, it is
possible to guarantee that bad CORBA references are not translated into bad
base language references (like dangling C++ pointers for example).  Instead,
the use of a stale reference generates an exception that is neatly handled by
the runtime and informed to the application.

As described in section \ref{sec:CC-implementation}, I have implemented this
model in Java and C++. I will extend these implementations to use Java RMI and
CORBA.  This will allow experimentation with different local and distributed
environments and with interoperability between distinct object models.



\subsection{Related Issues}

Discuss some related issues and tell what will be addressed by me and what
will be addressed by other students in the \twoK group.
- QoS
- Environments
- Security
- Naming
- Discovery/Trader

\subsubsection{Exception Handling}

This could be used for handling different kinds of exceptional behaviour
ranging from application-specific exceptions to fault handling leading to
graceful fault-tolerance.

\subsubsection{Reconfiguration Decision Making}

Who is going to take the reconfiguration decisions?

When should the system reconfigure itself?

Note that my framework does not decide when the components must be
reconfigured. This can be done by monitoring system state and adapting. This
will be addressed by the \twoK operating system but it is out of the scope of
this thesis.

\subsubsection{Quality of the Reconfiguration Service}

In practice, the configuration and dynamic reconfiguration of component-based
systems is subject to Quality of Service constraints. When a new application
is initiated, the user not only expects to receive full access to the
application functionality, but also expects some kind of quality in this
``initiation service''. The application should not take too much time to
initiate, the process should not cost too much, and the quality of the service
offered by the application should be the one expected.

In terms of dynamic reconfiguration, the quality is also very
important. Often, the need for reconfiguration arises from the desire to have
a better performance. If the reconfiguration process \emph{per se} utilize too
many valuable resources, there might be no performance gain at all.  Thus,
there is a need for careful consideration of the costs incurred in the
reconfiguration processes so one can estimate how convenient certain
reconfigurations would be. My research will analyze the costs of
reconfiguration so that QoS-aware adaptive systems can take this information
into consideration when evaluating if a system should be reconfigured or not.

\subsubsection{Security}

Controlling the access to the \class{ComponentConfigurator} is a critical
factor in determining the security of applications which use this model. By
modifying the dynamic dependencies among application components, a malicious
intruder might easily compromise the correctness of a process and even get
access to classified information and protected resources.

A CORBA implementation of this model can utilize the CORBA Security Service to 
ensure that access to the \class{ComponentConfigurator} operations are
controlled. Operations like \method{name()} and \method{info()} may be 
made available to a broad group of principals. But operations like 
\method{hook()} and \method{eventOnHookedComponent()} should be restricted
to trusted principals. 

The CORBA Security Service can be used to control the access to these sensitive
operations by requiring authentication. It can also be used to encrypt the
parameters that are sent in the method invocations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Completed Work}

In this section, I first describe the current implementation status of the model
previously presented. Then, I discuss the use of this framework in \dTAO.

\subsection{\class{ComponentConfigurator} Implementations}
\label{sec:CC-implementation}

I have implemented the \class{ComponentConfigurator} model as a framework in
both C++ and Java. The source code and documentation is available at 
\url{http://choices.cs.uiuc.edu/2k/ComponentConfigurator}. 
The C++ implementation was used in \dTAO as explained in section
\ref{sec:dynamicTAO} bellow. 

The Java implementation is being deployed by researchers at the University of
S\~ao Paulo to prototype a domain decomposition manager. This manager will be
applied to two demonstration applications: a Distributed Information System
for Mobile Agents \cite{SIDAM-SEMISH98} and the parallelization of an
Atmospheric Modeling System \cite{RAMS-98}.

\subsection{\dTAO}
\label{sec:dynamicTAO}

One of the major constituent elements of the \twoK distributed operating
system \cite{twoK:wroops98,2K:home} is a reflective middleware layer
based on CORBA. After carefully studying existing Object Request Brokers, I
came to the conclusion that the TAO ORB \cite{schmidt:tao-patterns98} would be
the best starting point for developing this infrastructure. 

TAO is a portable, flexible, extensible, and configurable ORB based on design
patterns. It uses the \emph{Strategy} design pattern \cite{ralph:patterns} to
encapsulate different aspects of the ORB internal engine. A configuration file is
used to specify the strategies the ORB uses to implement aspects like
concurrency, request demultiplexing, scheduling, and connection management. At
ORB startup time, the configuration file is parsed and the selected strategies
are loaded.

TAO is primarily targeted for static hard real-time applications such as
Avionics systems \cite{tao:avionics}. Thus, it assumes that, once the ORB is
initially configured, its strategies will remain in place until it completes
its execution. There is very little support for on-the-fly reconfiguration.

%The \twoK project seeks to build a flexible infrastructure to support adaptive
%applications running on dynamic environments. 
On-the-fly adaptation is extremely important for a wide range of applications
including the ones dealing with multimedia, mobile computers, and dynamically
changing environments.
%\twoK supports adaptation by monitoring system behavior and
%enabling on-the-fly reconfiguration of applications and middleware.

To support this kind of dynamic adaptations, I developed \dTAO, an extension
of TAO that enables on-the-fly reconfiguration of its strategies. \dTAO
exports an interface for loading and unloading modules into the ORB runtime,
and for inspecting the ORB configuration state. The architecture can also be
used for dynamic reconfiguration of servants running on top of the ORB and for
reconfiguring non-CORBA applications.

\subsubsection{Problems Encountered}

Reconfiguring a running ORB while it is servicing client requests
is a difficult task that requires careful consideration. There are
two major classes of problems.

Consider the case in which \dTAO receives a request for replacing one of its
strategies ($S_{old}$) by a new strategy ($S_{new}$). The first problem is that,
before unloading $S_{old}$, the system must be sure that no one is running $S_{old}$
code and that no one is expecting to run $S_{old}$ code in the future. Therefore,
it is important to assure that $S_{old}$ is only unloaded after the system can
guarantee that its code will not be called.

The second problem is that some strategies need to keep state
information. When a strategy $S_{old}$ is being replaced by $S_{new}$, part of
$S_{old}$'s internal state may need to be transfered to $S_{new}$.

\subsubsection{TAOConfigurator}

The problems described above can be addressed with the help of the
\class{ComponentConfigurator} framework. It is used to reify the dependencies among
ORB strategies, instances of \dTAO, and CORBA servants.

Each process running the \dTAO ORB contains a \class{ComponentConfigurator}
instance called \class{DomainConfigurator}. It is responsible for maintaining
references to instances of the ORB and to servants running in that
process. In addition, each instance of the ORB contains a customized subclass of
\class{ComponentConfigurator} called \class{TAOConfigurator}.

\class{TAOConfigurator} contains hooks to which \dTAO strategies are attached.
A \class{NetworkBroker} allows authorized principals to connect to the process
and change the way that \dTAO works by uploading code for new strategies,
dynamically linking new strategies, and attaching them to specific hooks. 
Local servants and remote CORBA clients can also access the
\class{Configurator} objects through a programmatic IDL interface.  Figure
\ref{fig:TAOConfigurator} illustrates this mechanism when a single instance of
the ORB is present.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode \epsfig{file=TAOConfigurator.eps,width=16cm}
    \caption{Remote Configuration of \dTAO strategies.}
    \label{fig:TAOConfigurator}
  \end{center}
\end{figure}

If necessary, individual strategies may have their own customized subclass of
\class{Component}\class{Configurator} to store their dependencies upon ORB
instances and other strategies. These subclasses may also store references to
client requests that depend on them. With this information, it is possible to
decide when a strategy can be safely unloaded.

Consider, for example, the three concurrency strategies supported by
\dTAO: Single-Threaded Reactive \cite{schmidt94:reactor},
Thread-Per-Connection, and Thread-Pool.  If the user switches from the
Reactive or Thread-Per-Connection strategies to any other concurrency
strategy, nothing special needs to be done. \dTAO may simply load the new
strategy, update the proper \class{TAOConfigurator} hook, unload the old
strategy, and continue. Old client requests will complete with the concurrency
policy dictated by the old strategy. Since their threads are already up and
running, they no longer need the old strategy code, it can be safely
unloaded. New requests will utilize the new policy.

However, if one switches from the Thread-Pool strategy to another strategy,
special care must be taken. The Thread-Pool strategy, developed in our
research group, maintains a pool of threads that is created when the strategy
is initialized. The threads are shared by all incoming requests to achieve a
good level of concurrency without having the runtime overhead of creating new
threads. A problem arises when one switches from this strategy to another
one: the code of the strategy being replaced cannot be immediately
unloaded. This happens because, since the threads are reused, they return to
the Thread-Pool strategy code each time a request is completed. This problem
can be solved by a
\class{ThreadPoolConfigurator} keeping information about which threads are
executing client requests and, if necessary, destroying them as the requests
complete. When the last thread is destroyed the Thread-Pool strategy
signalizes that it can be safely unloaded.

Another problem occurs when one replaces the Thread-Pool strategy by a new
one. There may be several incoming requests enqueued in the strategy waiting
for a thread to execute them. The solution is to use the \emph{Memento} pattern
\cite{ralph:patterns} to encapsulate the old strategy state in an object that is
passed to the new strategy. This object is used to carry the queue of
waiting requests. The system simply passes this object to the new strategy
which then takes care of the enqueued requests.

Our group is currently expanding the set of \dTAO strategies that can be replaced
on-the-fly. The \class{TAOConfigurator} will have hooks for holding strategies
for connection management, concurrency, marshalling, demarshalling, request
demultiplexing, method dispatching, scheduling, authentication, and encryption.

Explicit knowledge of the dependencies among the ORB components is
essential for implementing dynamic reconfiguration safely. This thesis will
provide a solid framework for supporting that.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Related Work}

\subsection*{Reflective Systems}

The idea of having a \class{ComponentConfigurator} object associated with
Components is similar to the concept of \emph{meta-objects} utilized by
reflective systems such as CLOS \cite{kiczales91:clos}, OpenC++
\cite{openC++}, Iguana \cite{dsg-97}, and Apertos \cite{apertos95}. 
In these systems, meta-objects can be used to customize all aspects of object
behavior.

Differently from that, the intent of the \class{ComponentConfigurator} is not to
modify the Component behavior but to maintain extra information about
inter-component dependence. This extra information helps the system to provide
fault-tolerance and automatic configuration and offers Components the
possibility of being aware of their dependencies.

\subsection*{SOS}

The idea of using prerequisites to represent the dependencies among
operating system objects was introduced in the SOS operating system \cite{SOS}
developed at INRIA, France. In the SOS model, objects contain a list of
\emph{prerequisites} that must be satisfied before an object is
activated. Even though the idea was promising, it was not fully explored in
that project. Prerequisites were only used to express that an object depends
on the code implementing it and not much experimentation was carried out
\cite{shapiro89:persistence,shapiro-personal}. SOS does not include a model
for dynamic management of inter-component dependence.

\subsection*{Composite Objects in Object Databases}

Bertino and Guerrini \cite{odmg:composite} extended the ODMG object database
data model to include the concept of \emph{Composite} objects. An
extension of the ODMG object definition language (ODL) is used to specify the
semantics of the dependencies between composite objects and their
components. Based on the ODL definition, the system propagates update and
delete operations across chains of composite objects. 

My framework differs from theirs in the sense that it is not limited to
database systems and that my framework is able to represent arbitrary
dependency relationships between components.

\subsection*{Workflow Models}

Shrivastava and Wheater \cite{reconfiguration:workflow} are currently working
on a workflow-based model for distributed applications. In their model, a
scripting language \cite{reconfiguration:workflow:language} is used to provide
high-level descriptions of \emph{workflow schemas}. Schemas represent the
structure of \emph{tasks} in a distributed application with respect to task
composition and inter-task \emph{dependencies}.

The meaning of the term ``dependency'' in their work is directly related to
the workflow model and differs slightly from the one I adopt. A dependency
can be either
\begin{itemize}
\item a notification dependency (meaning that a task can only
start its execution after its dependency has completed its execution) or a
\item dataflow dependency (meaning that a task needs to receive input data
from another task before starting its execution).
\end{itemize}

A \emph{workflow execution service} coordinates the execution of the workflow
and helps guaranteeing that reconfigurations will be performed in a
consistent way.  Each task is managed by a \emph{task controller} that handles
workflow dependencies and helps supporting reconfiguration.

A task is modeled as having a set of \emph{input sets} (analogous to my
\emph{hooks}) and a set of  \emph{output sets} (analogous to my
\emph{clients}). Their \emph{workflow schemas} resemble my 
\emph{prerequisites} slightly. Their \emph{task controller} resembles my 
\class{ComponentConfigurator}.

The main difference between the two models is that their model confuses the
representation of data flow, coordination, and inter-component
dependence. Their model is suited to expressing temporal workflow dependencies
among components in a certain application.  It does not address the
interactions between application components and system services.

However, it is important to note that they are able to specify what the
requirements for application tasks must be so that reconfigurations are
performed in a consistent way. I will further study related workflow models
and try to incorporate this ability in my model. In other words, I will try to
define requirements that Components must meet in order to guarantee that
they will be reconfigurable in a safe and consistent way.



\subsection*{Dynamic Loadable Libraries}

Modern operating systems, like Solaris for example, use an explicit
representation of the dependencies among shared libraries to implement dynamic
linking \cite{dynamicLinking97}. A shared library contains a list of other
libraries upon which it depends. The system tries to locate all the required
libraries before executing any application code. 

My approach may be seen as an extension to that since (1) it represents
dependencies among generic components in a heterogeneous distributed
environment and (2) it uses this representation to support different kinds of
reconfigurations (not only dynamic linking).

\subsection*{Microkernels}

Previous research in microkernels and customizable operating systems -- such as
Mach \cite{MachDesign}, SPIN \cite{bershad:spin}, L4 \cite{l4}, Exokernel
\cite{exokernel97}, and $\mu$Choices \cite{uc-java96} -- developed low-level
techniques for dynamic loading new modules to the operating system both in
kernel and user space. Nevertheless, a high-level model for operating system
reconfiguration is still inexistent.  These previous works have not addressed
a number of problems related to fault-tolerance and dynamic reconfiguration. 
Using the \class{ComponentConfigurator} framework, my research investigate
answers to the following questions.
\begin{itemize}
\item When a system module is replaced, which other modules are affected? 
\item How must those other modules react?
\item What is the cost of reconfiguring the system?
\item If a system component fails, how can the system detect it and recover
gracefully?
\end{itemize}
While answering these questions, this thesis will present a framework that
will help addressing the following questions.
\begin{itemize}
\item What are the consequences of reconfiguring the system? 
\item When (re)configuring the system, which components must be loaded to meet 
the service demand and the required quality of service?
\item When is time to reconfigure the system?
\end{itemize}

%\textbf{INCLUDE RELATED WORK ON
%\begin{itemize}
%\item other OSes: Spring, Globe, WebOS, Legion, Millennium.
%\item DYNAMIC RECONFIGURATION
%\item ADA and MODULA-2
%\item QoS and requirement specification languages
%\end{itemize}
%}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proposed Research Plan}

Organize this section in steps. Do not include time for completion.
Describe what are the refinements to the model that need to be done. Describe
the implementation plan.

\subsection{Theoretical Models}

\begin{itemize}
\item investigate representations for prerequisites. Simple prototype only. Move
what I wrote about it to this section.
\item Refine the model for runtime dependencies based on the experience with the
current implementation. Extend it to support nested components.
\item Define a set of requirements that applications must meet in order to
guarantee that the reconfiguration of their components can be carried out in a 
safe and consistent manner.
\end{itemize}

\subsection{Software Infrastructure}

\begin{itemize}
\item implement a very simple version of the prerequisite specifications. Design
the framework in such a way that different languages, and different ways of
representing them can be used. 
\item implement a simple pull-based code distribution mechanism so the
prerequisites can be fetched on demand. Implement a very simple CORBA-based
implementation repository to take care of that. If TAO's implementation of the
CORBA Standard Implementation Repository becomes usable, then consider using
it instead.
\item Extend the implementations to include nested components. Extend the
implementations to distributed environments: CORBA and Java RMI.
\end{itemize}

\subsection{Experimentation}

\begin{itemize}
\item Analyze the cost of reconfiguration in terms of latency and CPU and
memory utilization. Use profilers such as Rational Software's \emph{Quantify} to
analyze which parts of the reconfiguration consume what.
\item Analyze the performance of different ConcurrencyStrategies and the time that 
it takes to replace a ConcurrencyStrategy. So, in one particular case, we can
detect when reconfiguration is worthwhile.
\item using dynamicTAO to reconfigure the reflector.
\item So, I'll have 2 applications to exercize the CC framework. One is a
centralized, C++ one (dynamicTAO) and the other is a distributed CORBA-based
one. Think more about this. Am I going to use the CC to represent the dataflow 
between the reflectors and support fault-tolerance in case one of the
reflectors in the network fail???
\end{itemize}

\section{Conclusions}


\bibliography{/home/guests/f-kon/lib/bib/2k,/home/guests/f-kon/lib/bib/dfs,/home/guests/f-kon/lib/bib/paper,/home/guests/f-kon/lib/bib/ChoicesRef,/home/srg/singhai/LaTeX2e/net-multi}

\end{document}


