An interactive application responds to aperiodic user input with
computation that can be expressed as activation trees. By bounding the
execution time of these trees, we can improve the responsiveness of
the application.  The application runs in a typical computing
environment: a group of uncoordinated but measurable hosts
interconnected with a measurable local area network.  The environment
serves a number of independent users and we do not control it.
However, using a remote execution mechanism, we can execute each node
(procedure call) of a tree on any host on the network.  We want to use
this freedom by dynamically mapping nodes to hosts in order to maximize
the percentage of trees that execute within their allotted time.

My thesis is that this dynamic mapping problem can be solved using
history-based prediction.  In essence, the idea is to monitor the
system and the application and use the measurements to predict how
their behaviors will evolve.  Each node is then mapped to the host
which best serves to match the predicted future application behavior
to the predicted future system behavior. 

We present two strong pieces of evidence that argue that this is an
effective approach.  The first is an extensive analysis of host load
traces on a wide variety of host systems which strongly suggests that
load can be predicted from its history.  The second is a history-based
prediction algorithm that achieves near optimal performance for a
simplified variant of the problem.

For my thesis, I will extend these results to develop a history-based
prediction algorithm for the full dynamic mapping problem.  The
algorithm will be developed using a realistic trace-driven simulation
environment based on host load traces, network traces, and traces of
activation trees collected from real applications.  Because of its
highly realistic nature, I intend to also evaluate the algorithm using
the simulator and a set of benchmarks.  In addition, I will
incorporate my algorithm into a distributed object system to show that
it can work in a real system.