\section{Related work} \label{sec:related_work} In this section, we discuss related work in applications, remote execution facilities, distributed soft real-time systems, and quality of service systems. \subsubsection*{Applications} There is considerable interest in distributed interactive applications for visualizing and steering scientific computations, manipulating media, and playing games. The goal of the thesis work is to simplify building these sorts of of applications. Scientific visualization involves the useful display of large, complex datasets, while computational steering lets the user use this display to focus a running physical simulation on areas of interest~\cite{FOCUS-ON-SCIENTIFIC-VISUALIZATION-BOOK}. For example, the CAVE project~\cite{CAVE-INPROCEEDINGS} involves connecting immersive virtual environment simulators to remote physical simulations. CAVE has also proven to be a good environment for scientific and engineering collaboration~\cite{COVISE-INPROCEEDINGS}. Cumulus~\cite{CUMULUS-INTRO} is a library and run-time system for adding adding visualization and computational steering to simulations based on iterative operations on dense matrices. Tele-operation is related to computational, except that the remote physical simulation is replaced with an actual physical system. Tele-operation systems such as the one discussed in~\cite{APP-DRIVEN-APPROACH-NET-MM-SYS}, involve operating robots by remote control over conventional networks. While most current distributed multimedia systems involve communicating and synchronizing different audio and video streams, manipulating media on a distributed system in computationally significant ways is becoming increasingly important. For example, medical imaging systems~\cite{OO-FRAMEWORK-HS-MEDICAL-IMAGING}, involve acquiring, processing, storing, and making medical images easily available to physicians no matter where they are. Next generation stream-oriented systems like the VuSystem~\cite{VUSYSTEM-INPROCEEDINGS} filter the streams in computationally intensive ways, such as extracting titling text from video streams. Image editing programs such as Photoshop~\cite{PHOTOSHOP-MANUAL} were also ripe for distributed systems because of the increasingly huge size of photographic images~\cite{NET-COMP-WORLD-SIM-TECHREPORT}. Games are becoming increasingly interesting applications for distributed systems. For example, the Department of Defense's DIS effort is trying to create large scale (100,000 users or more) simulated war games by connecting different kinds of simulators located all over the world~\cite{DIS-VISION-TECHREPORT}. At least three companies, Silicon Graphics, Zombie Entertainment, and Military Simulations, Inc., are working on extending the emerging DIS technology for civilian games, with an example of a DIS-based game being shown at SIGGRAPH '96. In addition to multiplayer games, we expect that single player games will become increasingly rely on computationally intensive physical simulations for realism. For example, the use of physically based acoustics and music~\cite{GEOMETRIC-ROOM-MODELING,VIRTUAL-INSTRUMENTS-VIRTUAL-ROOMS,PHYSICAL-MODELING-SYNTHESIS-UPDATE} in games may not be far off. \subsubsection*{Remote execution} Our machine model includes a remote execution facility, which allows a procedure call to be executed on any host in the system. The purpose of our work is to decide which host is best for a given call. Examples of remote execution facilities include remote procedure call systems, distributed shared memory mechanisms, and distributed object systems. Remote procedure call systems~\cite{RPC-BIRRELL-NELSON,LIGHTWEIGHT-RPC-BERSHAD}, such as the one specified by the DCE~\cite{DCE-INTRO} standard, provide a procedure call-like abstraction over network communication with a remote server. Distributed object systems~\cite{DO-SURVIVAL-GUIDE-BOOK,CHIN-DO-PROGRAMMING-SYSTEMS}, such as CORBA~\cite{CORBA-INTRO-ARTICLE,CORBA-20-ARCH-SPEC-TECHREPORT,CORBA-FUND-PROG-SIEGEL-BOOK}, DCOM~\cite{DCOM-RFC-DRAFT} and Java RMI~\cite{JAVA-RMI-SPEC}, extend the RPC abstraction to objects by allowing the association of state with a group of procedures. Distributed shared memory systems such as Tempest~\cite{TEMPEST-TYPHOON-ISCA}, Shasta~\cite{SHASTA-ASPLOS}, and ThreadMarks~\cite{THREADMARKS-ASPLOS} provide the appearance of a global address space shared by some number of private memory hosts. This is combined with a multithreading model where threads that may be assigned to different hosts communicate via shared variables. Although today's common remote execution facilities have relatively high overheads in the millisecond range~\cite{PERF-COMM-MIDDLEWARE-HS-NET}, our experience is that this is due mostly to the latency of network protocol stacks and we expect that this latency will improve. With microsecond range application-to-application communication latencies such as the PAPERS network~\cite{BITWISE-AGGREGATE-NETWORKS} can provide, the overhead of remote execution in a system like LDOS or CORBA could be within a couple of orders of magnitude of the overhead of a local call.~\footnote{The marshalling/unmarshalling and dispatch overhead of a call in LDOS is only about 100 times greater than that of a C++ virtual function call.} Such an improvement would drastically increase the fraction of procedures in a typical program that could be profitably executed remotely. \subsubsection*{Dynamic load balancing} Dynamic load balancing involves assigning tasks to hosts at run-time or moving tasks from one host to another at run-time in order to maximize some performance metric. Common performance metrics include the throughput of the system, the mean execution time of tasks, or the actual running time of an application. In contrast, the goal of our work is to maximize the number of tasks (activation trees) that meet their time bounds. There are both operating system-centric and application-centric approaches to dynamic load balancing. Our work is wholehearted application-centric --- we want to predict the behavior of the rest of the system in order to improve the performance of one specific application. However, we share an important question with both forms of dynamic load balancing: how can an individual host in a distributed system be aware and predict the behavior of the system as a whole in a scalable, practical way? The goal of operating system-centric dynamic load balancing is usually to maximize the throughput of the distributed system as a whole. The idea is to schedule independent, sequential tasks on a group of hosts such that each host has approximately the same load. A distinction is sometimes drawn between load sharing~\cite{RESOURCE-BASED-POLICIES-LOAD-DISTRIBUTION} (also called load distribution and load leveling), which offers only a rough approximation to equalizing load across the hosts, and load balancing, which attempts more precision~\cite{COMPARISON-SENDER-RECEIVER-LB-STRAT-EAGER}. In either case, the distributed operating system is comprised of host-local schedulers which interact to implement transfer (should task be moved?) and location (where should task go?) policies~\cite{ADAPTIVE-LOAD-SHARING-HOMOGENEOUS-EAGER}. In our work, we schedule dependent tasks (activation tree nodes) and do not balance loads across different hosts. Early work in operating system-centric dynamic load balancing assumed simple, analytically tractable distributions for job length and other properties. Under these assumptions, simple heuristics and initial placement were found to be adequate~\cite{LIMITED-BENEFIT-MIGRATION-EAGER,COMPARISON-SENDER-RECEIVER-LB-STRAT-EAGER}. However, measurement studies~\cite{LOAD-BAL-HEURISTICS-PROCESS-BEHAVIOR-LELAND-OTT} have cast doubt on these assumptions, and more recent work~\cite{EXPLOIT-PROC-LIFETIME-DIST-DYN-LB-SIGMETRICS} argues strongly for process migration. This is an important result for our work, since it argues for dynamically mapping individual activation tree nodes (letting the computation migrate at procedure call points) as opposed to mapping the whole tree (initial placement of the whole computation.) The goal of application-centric dynamic load balancing is to minimize the execution time of a single, typically parallel application. For example, in data parallel applications built in DOME~\cite{DOME-TECHREPORT}, neighboring hosts periodically exchange measurements of execution time and redistribute their data accordingly. The system described in~\cite{SIEGELL-DYNAMIC-LB-94} uses a global approach where one centralized agent makes load balancing decisions based on execution times reported by all of the hosts. Jade~\cite{JADE-LANGUAGE} load balances unfolding task parallel computations by dynamically mapping task graph nodes to hosts to minimize communication and overall execution time. In contrast, our work dynamically maps activation tree nodes that are executed sequentially. In order to be scalable, a dynamic load balancing system pursues its global policy by making local decisions based on limited or outdated knowledge of the system as a whole. Based on this limited knowledge, a local scheduler estimates the current state of the system and makes its decisions based on that estimate. By exploiting subtle properties of specific distributed systems or application workloads, some systems can put their limited knowledge to better use. In essence, this is what we intend to do for a specific class of applications. One example of exploiting such properties is Hailperin's thesis~\cite{LOAD-BAL-TIME-SERIES-STAT-PERIODIC-LOADS-HAILPERIN}, which takes advantage of the statistical periodicity of his sensor-driven applications. Our applications have aperiodically arriving activation trees. In~\cite{ADAPTIVE-LOCATION-POLICIES-GLOBAL-SCHEDULING}, the authors present location policies that adapt to system load to avoid instability. Mehra and Wah~\cite{AUTOMATED-LEARNING-WORKLOAD-MEASURES-LB} use comparator neural networks to predict current workload indices on remote hosts using outdated information about resource utilization. Mehra's thesis~\cite{AUTOMATED-LEARNING-LOAD-BALANCING-STRATEGIES-MEHRA} describes a whole load balancing system based on automated strategy learning using comparator neural networks. We have also found some success with a neural networks approach. Indeed, it is interesting to note that machine learning~\cite{MACHINE-LEARNING-MITCHELL} approaches are also finding success in related scheduling problems. For example, genetic algorithms have been successful in branch prediction~\cite{LANG-PRED-AUTO-SYNTH-GAS-EMER} and scheduling loop level parallelism in multiprocessors~\cite{MULTIPROCESSOR-SCHEDULING-GENETIC-ALGS}. \subsubsection*{Distributed soft real-time systems} A real-time system allows a programmer to specify a deadline for the execution of a one-time or periodic task. The bounds in our dynamic mapping problem correspond to these deadlines. However, while real-time systems typically provide some form of guarantees, our work is strictly best effort. Further, most real-time systems require control of the entire computing environment, either via resource reservation or priority-based scheduling. In contrast, we control only the mapping of activation tree nodes to hosts. A hard real-time system is one which is only correct when every task in the system always meets its deadlines. These systems are necessary for some applications, but are very difficult to build, place many constraints on the hardware, and typically require knowledge of all tasks at design time. The rate-monotonic scheduling and earliest deadline first scheduling algorithms~\cite{RMS-EDF-SCHEDULING-LIU73} can be used to produce feasible schedules for fixed sets of tasks with known characteristics. Distributed hard real-time systems have been built (eg, MARS~\cite{MARS-SURVEY}), but these tend to rely on specialized hardware. In contrast, our work offers only a best effort service, but the tasks and deadlines are discovered only as the program is executed. A soft real-time system is one where it is permissible for some tasks to miss their deadlines. What it means to miss a deadline depends on the system. A common approach is is to generalize a deadline into a utility function of the duration since the task arrival time~\cite{REAL-TIME-MANIFESTO-JENSEN}. The system then attempts to maximize the collective or individual utilities of tasks in the system. The functional form of a hard deadline in this kind of system is a unit step function. While the general case of this scheduling/optimization problem is quite complex, by constraining the form of the utility function, tractable specialized scheduling algorithms can be developed. The common underlying mechanism in soft real-time is a fixed priority scheduler combined with priority inheritance to address priority inversion. In a fixed priority scheduler, each task is assigned a fixed priority and the scheduler always runs the highest priority task that is ready to run. Unfortunately, very few general purpose operating systems actually implement fixed priority scheduling. In contrast, we have a very simple performance metric (the percentage of activation trees that meet their deadlines) and our work does not require specific kinds of schedulers or any real control over the system other than a remote execution facility and measurement facility. Achieving soft real-time goals in a distributed system is very difficult since the system is much larger and more complex. One approach is to create a notion of a global priority, require that all resources in the system be scheduled by fixed priority schedulers that respect the fixed priority, and require that all communication delays be bounded. This is the approach taken in~\cite{RT-RMI-DIST-ENV-RI} and in proposals to the Real-time CORBA standardization effort~\cite{REALTIME-CORBA-WHITEPAPER,TIMING-CONSTRAINTS-CORBA-RI}. Another approach is to implement resource schedulers that provide reservation mechanisms, such as in SONIC~\cite{PREDICTABLE-NETWORK-COMPUTING}. In contrast, we make no attempt to control the system in order to meet our goals. Rather, we monitor and predict the system in order to adapt the application's behavior (the mapping of activation tree nodes) to the system and meet our bounds. As in dynamic load-balancing, a key challenge in distributed soft real-time systems is how to scalably coordinate the actions of many local schedulers. If a task is submitted at a host where it cannot meet its deadline, we would like to move it to a host where it is likely to be able to. However, that host's knowledge of other hosts is limited and out of date. Bestavros and Spartiotis suggest a scheme in which simple stochastic models of other hosts' load conditions are formed based on infrequent, opportunistic information exchanges and task mappings are chosen probabilistically from among hosts that qualify according to the models~\cite{PROB-JOB-SCHED-DIST-RT-BESTAVROS}. Bestavros extends this work by arguing that load balancing is actually detrimental to real-time performance and develops an alternative which intentionally tries to keep loads out of balance and makes task mapping decisions based on the underlying load profile it is trying to maintain~\cite{LOAD-PROFILING-BESTAVROS}. We suspect that Bestavros has more success with simple stochastic models than we do because he is modeling the remote schedulers that are a part of his system and are therefore a known quantity. In addition to load balancing, Hailperin's thesis~\cite{LOAD-BAL-TIME-SERIES-STAT-PERIODIC-LOADS-HAILPERIN} also takes advantage of the statistical periodicity of his sensor-driven applications to help place and migrate objects so that method invocations meet their deadlines. We must deal with aperiodically arriving activation trees. \subsubsection*{Quality of service} Quality of service, or QoS, is a fairly generic, but nonetheless widely used term to describe providing a more predictable environment for applications. In this sense, our work can be seen as a QoS service for a specific class of applications. In the networking community, QoS has meant providing deterministic and statistical guarantees of the bandwidth and latency of connections for media applications~\cite{FERRARI-REQUIREMENTS-RT-COMM,KUROSE-OPEN-ISSUES-QOS}. Tenet~\cite{FERRARI-MM-NET}, RSVP~\cite{RSVP-RFC} and the ATM CBR and VBR service classes are examples of network QoS systems. Although we make no assumptions about the network, one could imagine using such mechanisms to simplify the dynamic mapping problem by making the communication costs known a priori. Recently, interest has focused on how to expose network and host QoS features to the application programmer in an understandable fashion. For example, work at BBN~\cite{ARCH-SUPPORT-QOS-CORBA-BBN,QOSO-OVERVIEW-BBN} is considering how to express QoS requirements and guarantees for distributed objects in a collaboration system and similar applications. The challenge is in translating between the object level and the network level and in providing a clean way for the programmer to identify different regions of operation and when to switch between them. Another example of translation and adaptation involves the Qual language being developed at Columbia~\cite{QUAL-PROPOSAL}. Qual is a language for expressing the quality requirements of program modules. These specifications can then be compiled into a monitoring agent which switches between different regions of operation. Compilable specification languages to support binding modules and services have also been developed in the parallel computing community. DURRA~\cite{DURRA-BARBACCI} is a well known example. In our work, the bounds placed on the execution time of an activation tree could be seen as a QoS specification. In mobile computing the QoS challenge is to detect changing wireless network conditions quickly and adapt to them gracefully. For example, the Odyssey system~\cite{ODYSSEY-SOSP97} provides the application with typed data streams (eg, video) and switches between different quality levels (data rates) as it detects changing available network bandwidth. When quality strays outside of the range that the application registered initially, an upcall is made to the application, which decides the course of action.