\section{Introduction}

Our vision is to harness the combined resources of millions of
computers connected to the Internet, forming a powerful heterogeneous
computing environment for running coarse-grain parallel
applications.
%
%Large simulations that faithfully model reality often require enormous
%computational resources.
%Several compute-intensive applications, such as Gaussian and VLSI simulations,
%already have been successfully distributed onto cluster-of-workstation
%environments.  Many companies maintain large clusters of workstations dedicated
%to running such applications, using packages such as PVM, Linda, or Condor for
%communication and load-balancing.  For example, digital imaging companies
%frequently use large clusters for rendering computer generated movies (e.g.,
%Toy Story).  In all of these cases, the computational resources are connected
%through a LAN that belongs to a single entity, and thus usually are limited in
%scale.  Furthermore, installing these systems requires a fairly high
%administrative overhead and possibly human cooperation across different
%departments.  Also, since each organization usually purchases its CPU time
%according to its maximum intended usage requirements, utilization is low.
%
Cluster computing and network of workstations in a LAN setting already
are being used extensively to run compute-intensive applications.
%
%Of late, Internet-based Computing involving thousands of computers has been a
%very active area of research.  It
On a more global scale, Internet-based cluster computing involving thousands
of computers, recently has demonstrated its usefulness for several
important and news-breaking applications.  In November 1996, a PC in France
running for 88 hours found the 35th known Mersenne prime, the largest known
prime discovered so far \cite{gillmor96}.  This computer was part of a
world-wide distributed computing effort for finding large primes, involving a
group of more than 700 workstations and PCs.  Then, in January 1997, RSA
announced a code breaking challenge.  Within only 3.5 hours, a graduate student
at Berkeley had cracked the 40-bit RSA code running on a 128-processor
UltraSparc NOW cluster~\cite{lash97a}.  Two weeks later, the 48-bit RSA code
was cracked using 3,500 workstations spread across Europe~\cite{lash97b}.  On
June 17th, 1997, the 56-bit DES~\cite{rsa97} was cracked, using approximately
78,000 computers, as many as 14,000 per day.  The press
release~\cite{deschall_press97} states:
\begin{quote}
{\em
This project demonstrates the kind of supercomputing power
that can be harnessed on the Internet using nothing but ``spare'' CPU
time.  ``Imagine what might be possible using millions of computers
connected to the Internet!''  Aside from cryptography and other obvious
mathematical uses, supercomputers are used in many fields of science.
``Perhaps a cure for cancer is lurking on the Internet?'', said Verser,
``Or perhaps the Internet will become Everyman's supercomputer.''
}
\end{quote}

The above examples illustrate that large numbers of users are willing to
participate in global computing efforts and that there are applications that
can be run very efficiently in wide area networks.
%The above examples,
While dramatic and encouraging, they also show that of the tens of
{\em millions} of computers connected to the Internet, only a small percentage
participate.  There are  several reasons for this.  Security is of foremost concern.  
Participation requires either
downloading and running an executable, or downloading unknown source code and
then compiling it.  The code may contain bugs or viruses that can destroy or
spy on local data.  Secondly, participating in such a computational challenge
is not easy.  Each of the examples mentioned above, runs on a different set of
architectures, and requires different mechanisms to download and participate.
Finally, participants currently do so voluntarily, donating idle
computing time that otherwise would have been wasted.  There is no incentive
provided beyond either curiosity, helping a worthy cause, or fame (if one is
lucky enough to find the key).  We believe that lack of security, lack of a
unified framework, and lack of incentive are key reasons explaining the small
participation.
%why, of the tens of {\em millions} of computers connected to the
%Internet, only a small percentage participate.

%Several recent projects, such as Legion \cite{grimshaw97}, Charlotte
%\cite{baratloo96}, Atlas \cite{baldeschwieler96}, ParaWeb~\cite{brecht96},
%and Popcorn~\cite{Camiel97} share the vision of seamlessly integrating
%networked computers into a global computing infrastructure.
%They have identified many of the issues, and address them holistically.

The advent of a safe and portable language system such as Java has provided
tools and mechanisms to address these issues and interconnect computer systems around the globe
in cooperative work efforts.  We contribute to this goal by developing a
flexible, scalable, easily-installed infrastructure for
running coarse-grained distributed applications on any Internet machine.


\subsection{Concept and Architecture}

We have implemented a Java-based global computing infrastructure called
{\em Javelin}.  In our model, there are three kinds of participating entities:
brokers, clients, and hosts.  A {\em client} is a process seeking computing
resources; a {\em host} is a process offering computing resources; a
{\em broker} is a process that coordinates the supply and demand for computing
resources.  Figure \ref{fig:arch} illustrates our architecture.
Clients register with the broker their tasks to be run; hosts register with the broker their
intention to run tasks.  The broker assigns tasks to hosts that,
then, run the tasks and send results back to the clients.  The role
of a host or a client is not fixed.  A machine may serve as a Javelin host
when it is idle (e.g., during night hours), while being a client when its
owner wants additional computing resources.

\begin{figure}[htbp]
\centerline{\psfig{figure=figs/architecture.eps,width=3in,clip=}}
\caption{\em {The Javelin Architecture.}}
\label{fig:arch}
\end{figure}

%
%\begin{figure}[htbp]
%  \centerline{\psfig{figure=figs/model.ps,width=4in,clip=}}
%  \caption{\em {The Javelin Architecture. {\bf Another picture?}}}
%  \label{fig:arch}
%\end{figure}
%

\subsection{Goals and Philosophy}

Our most important goal is {\em simplicity}, i.e., to enable everyone
connected to the Internet or an intranet to {\em easily} participate
in Javelin.  To this end, our design is based on widely used
components: Web browsers and the interoperable language Java.  By simply
pointing their browser to a known URL of a broker, users automatically
make their resources available to host part of distributed computations.  
This is achieved by downloading and executing an
applet that spawns a small daemon thread that waits and ``listens'' for
tasks from the broker.  The simplicity of this approach makes it easy
for a host to participate---all that is
needed is a Java-capable web browser and the URL of the broker.

The infrastructure is also simple to use for clients.  When a client
wants to run a job, it first contacts the broker, again by pointing
the web browser to a specific URL.  It then provides the broker with
the necessary program code in the form of a Java applet.  The broker, in
turn, schedules the jobs, distributing the program code among the
available hosts.  In our basic implementation, we do not even assume
that a client has an HTTP server.  All it needs is a web browser
for uploading applets and spawning threads.

%Additionally, since dial-up accounts and mobile computing are common,
%clients can disconnect from the network after submitting a task, and retrieve the result later.  
%Similarly, hosts can receive a task, compute it off-line, and then re-establish the network %connection to return the results. 

The key technology underlying our approach is the ability to safely
execute an untrusted piece of Java code sent over the Internet,
something most WWW browsers can do (assuming all security bugs have
been fixed).  While existing Java virtual machines currently have a
high interpretation overhead, new technologies such as just-in-time
compilation, dynamic compilation, and software fault isolation are
becoming commercially available.  These will eliminate most
of the interpretation overhead, allowing Java programs to execute both safely and efficiently.   
Since a standard WWW browser can
register CPU time at the user-level, no changes to the operating
system have to be made.  We therefore expect tens of thousands of hosts to
participate.


\subsection{Scope of our Work}

The purpose of this work is to provide a simple yet efficient
infrastructure that supports as many different programming models as
possible without compromising portability and flexibility.  
As discussed in \cite{superweb97}, there are several important
issues such an infrastructure must provide to be successful.
In this paper, we do not attempt to study these issues, but instead
focus on a particular design, discussing the constraints imposed by
standard, Java-enabled web browsers.  Future
versions however will take these aspects into account.
These issues include:

\begin{description}
\item[Ease of use:]
Ease of use is a key property of Javelin,
since it relies on the participation of thousands of users.  Our approach is
{\em web-centric}, where a user needs only 
a Java-enabled web browser to participate.

\item[Security:]
Hosts must be able to trust the programs being executed on their machines.  
We therefore assume the usual Java security restrictions that apply to applets.  
For example, applets downloaded from the broker are permitted to communicate with
the broker only.  Additional Java security issues are discussed in
\cite{DFW96}.  In this version, we do not provide levels of security beyond
what Java-enabled Web browsers offer.
%However, we expect that signed applets will allow us to construct a secure
%execution environment that is more flexible.

\item[Scheduling and Load Balancing:] Since brokers cannot know
  the semantics of particular applications, the client ultimately is
  responsible for {\em scheduling} tasks. {\em Load balancing} in its simplest
  form is achieved through the broker network either by contacting other brokers for help,
  if local hosts are busy, or by ``work-stealing'' from other brokers, if local resources
  are idle. Beyond this, we do not enforce any specific algorithm.

\item[Fault Tolerance:] It is desirable for the network of brokers to
  provide some form of {\em fault tolerance}.  However, in this
  version we do not concentrate on this issue. The client can provide
  some degree of fault tolerance itself, e.g., by duplicating subtasks
  and rescheduling them if results do not arrive.

\item[Economic Incentive:] Participation in such a global computing
  infrastructure must be encouraged by providing hosts with benefits
  (e.g., digital cash or bartering computer resources). The
  construction of such exchange mechanisms can be undertaken with the
  tools provided by Javelin.

\item[Result verification:] Clients must have some level of assurance that the results received from anonymous hosts are correct.  Assurance methods exist for some kinds of computations.
For general computations, it appears to be an interesting research topic. 

\item[Privacy:] Clients may want to secure their program and data from spying by hosts.

\end{description}

The initial implementation of Javelin can be used by organizations with intranets
consisting of a large number of heterogeneous computers.  
Running within a restricted intranet simplifies many security, privacy, and network performance issues that are present in full Internet deployment.

\subsection{Contributions and Outline}
We present a system that makes it easy for computers all over the
world to cooperate in distributed computations. 
This paper is organized as follows.
Section \ref{design} identifies some architectural implications of
using a heterogeneous, secure, Internet execution environment, in the
form of Java applets running under standard Web browsers.  Section
\ref{prototype} presents a set of abstract behaviors that must be
implemented to realize the architecture, and discusses some
implementation tradeoffs.  We also present the design and
implementation of a portable and flexible infrastructure, called
Javelin, and illustrate how it can be used to implement several
programming models, including the Linda tuple space, and SPMD
programming.  Section \ref{sec-results} presents measurements of
Javelin's current performance on two popular distributed applications:
Mersenne Primes and ray-tracing.  These measurements shed light on
those aspects of the system that would most benefit from greater
efficiency.  Section~\ref{sec:related} discusses related work and
Section~\ref{summary} concludes.





%Currently, many people are working on
%building an infrastructure to support global distributed
%processing. Examples of current efforts are the ATLAS system
%\cite{BBB96}, ParaWeb
%\cite{BSST96}, or Charlotte \cite{BKKW96}. These examples will be further discussed
%in Section \ref{Relat}.
