\section{Technical Issues}
\label{sec:enabling}

The computing environment we envision has several unique properties
that, taken together, distinguish it from other distributed systems
and pose challenging technical problems that need to be addressed.

\begin{description}
\item[Interoperability:] The participating computers are {\em
    heterogeneous}, meaning that they have different CPUs and run
  different operating systems. This complicates the transfer of
  programs between clients and hosts. Different solutions are
  available: For instance, portable, interpreted bytecode (e.g.,
  Java bytecode) might be used.  Alternatively, source code
  or precompiled binaries might be sent to
  hosts capable of executing such tasks.
  
\item[Execution speed:] When executing portable code the host has
  to translate them to its native machine language.  Whether done by
  interpretation or by compilation, translation presents execution
  overhead. Furthermore, providing host 
  security incurs additional run-time overhead.
        
\item[Security:] Except for the broker, all participants 
  in SuperWeb are untrusted:
  the client and  the host need not trust, or even know of, one
  another. As a consequence their interaction raises a variety of
  security problems for hosts as well as clients.
  
\item[Communication:] SuperWeb is a {\em global} environment in which
  the participating computers can be thousands of miles apart.
  Communication between the client and the host, and between
  cooperating hosts of a distributed task can be quite slow or even
  unreliable, unlike in a tightly coupled parallel machine or in a
  network of workstations. This limits the class of parallel
  applications that we can run efficiently.
        
%\item[Other issues.] One feature of our design is that the client and
%  host software runs entirely at the {\em user level}, requiring no
%  modifications to the underlying operating system, or even system
%  administrator support. This encourages the wide use of our
%  environment, but makes the implementation more challenging. Another
%  problem we have to address  is general fault tolerance, since the
%  communication links we use are notoriously unreliable, and likewise
%  we cannot trust the hosts, either.

\end{description}

Although these are difficult problems, a lot of research has
focused on them. As we show in the following paragraphs, solutions
to most of the individual problems are already available.


\subsection{Interoperability}
The key operation in SuperWeb is {\em task shipping}:
submitting tasks from \emph{any} client to \emph{any} host.
%
This is easy to achieve in a homogeneous system where all machines are
compatible, since then binary executables can be sent.
Unfortunately, in a heterogeneous environment like the Internet, hosts
and clients may have different instruction sets, integer/word sizes,
or operating systems.  Generally, there are two different ways to ship
tasks: using multiple binary executables or using a machine
independent language.

Machine independent code is the straight-forward way to allow
arbitrary machines to execute one another's code.  With this approach,
the client compiles its task to the machine independent language and
then sends it to the host. The host executes the task either by
interpreting it, or by compiling and then running it.
Java~\cite{CosMcG95} employs this approach.  It defines both a
high-level programming language for writing programs and a
machine-independent virtual machine language, Java bytecode.  Although it
provides additional compatibility and security guarantees, it is not
necessary to invent a new high-level language in order to ensure
portability. For example, Omniware \cite{omniware95} only defines a
machine-independent task shipping language and any high-level language
can be compiled to it.
  
Another feasible solution is to submit tasks as machine-specific
binaries.  This offers high execution speed, but limits the choice of
hosts on which the task can run in a heterogeneous environment.  In an
organization's mini-SuperWeb, encompassing only homogeneous machines,
this might be the most effective solution. In a heterogeneous
environment, the broker is responsible to map tasks to compatible
hosts only.


\subsection{Execution speed}
One of the main reason people would submit tasks for execution on
remote computers is that their own machine alone does not provide enough
performance. Therefore, if SuperWeb is to succeed, it
must provide fast task execution. This can be achieved either by using
binary executables for task shipping or by using a portable language
in combination with modern compilation techniques and optimizations.

Currently there is a misconception among many users that portable
languages like Java are inherently slow. This perception is
due to high interpretation overhead present in current Java implementations
which results in a 5-50 times slowdown compared to compiled
C code. Fortunately this is not a fundamental problem with portable
code, but rather a shortcoming of current implementations. 
For example, in the Omniware \cite{omniware95} 
system the portable code is compiled
to machine code at the host before execution. As a result Omniware
tasks run within 9.3\% of native machine code.
Even for Java, modern techniques such as just-in-time (JIT)
compilation  and dynamic compilation can eliminate most of the
interpretation overhead by compiling
pieces of the application to machine code. Using these approaches,
Java bytecode code can be executed at a speed close to that
of compiled C code. 
Commercial just-in-time compilers from a number of vendors are readily
available, and the ubiquitous Netscape browser uses JIT techniques for
some platforms.

If the ultimate in execution speed is necessary, tasks can be shipped
as plain machine binaries. Theoretically this should ensure execution
speed equivalent to that of native machine code. This is indeed
possible if the host trusts the client and is willing to run the
executable without any security precautions.
In practice there is always extra overhead that comes from the safety
checks needed to guarantee the security of the host. 

\subsection{Host Security}
Executing an anonymous piece of code poses integrity and security
threats to the host. Consider the dangers of downloading a binary
executable from some anonymous FTP site and using it.  A buggy binary
executable can interfere with other running applications or, in some
operating systems, crash the whole machine.  A malicious executable
(e.g., one containing a virus or a Trojan horse) can delete important
files or secretly transfer sensitive data of the unsuspecting user.
Observe that these dangers are not limited to binary executables.
Rather, they come from the fact that the anonymous program has
unlimited access to system resources.  An interpreted program may
cause as much damage as a binary executable if the interpreter does
not limit its access to memory, files, network, CPU usage, and other
resources.\footnote{ A typical example is
  the ghostview interpreter for postscript. Numerous security bugs
  were discovered in this interpreter.}
 To deal with these dangers, the host should run untrusted
code inside a confined environment that allows only limited access to
system resources.
%
% Observe that almost all real-life
% programming languages allow the potentially dangerous operations
% because they are necessary
% for a language to be usable. For example,
% The specifications for Java bytecode and Omniware modules
% impose little (Java), or no (Omniware) restrictions on what programs
% can do.
%
% Therefore the security of the host executing Java or Omniware
%code greatly depends on the protection provided by the
% implementation of the Java VM interpreter or the OmniRun runtime system 

Confining untrusted programs is technically simple to achieve when the
code is being interpreted. Since every single instruction is executed
under the control of the interpreter, the interpreter can check the
instruction arguments to ensure that all accesses are legal before
executing the instruction.  For example, two existing Java-enabled web
browsers guard file and network accesses, as well as system calls.
HotJava allows the user to select the strictness of the policy while
Netscape
%
% \footnote{ This applies for Netscape Navigator version 2.0b3.}
%
prohibits all local file accesses and allows network connections only
to the server from which the applet was downloaded. The ``E''
programming language \cite{elang}, which basically is a spiced-up
version of Java, provides for a more general and flexible framework to
define the capabilities of downloaded code.


Ensuring protection for the host for compiled code or plain
binary executables is more complicated
since there is no controlling entity that can check every instruction
for safety.
The recently developed technique of
{\em Software Fault   Isolation} (SFI) \cite{omniware95}
inserts the protection checks in the machine code itself.
SFI allows the safe execution of arbitrary
untrusted  binaries. Before running a piece of machine code,
it is instrumented
by placing safety checks in front of every potentially dangerous
instruction. Later, at run time, if a safety check determines that
the executable is about to access a prohibited resource,
% (memory location, disk file, network address, etc.)
the perpetrating instruction is aborted. 
Other variations of SFI  \cite{GoldbergWTB96} do not modify the
executable at all, but instead use operating system specific 
mechanisms to intercept and screen dangerous system calls. 


%  For the excution of \emph{arbitrary} binaries or
%  scriptfiles, the possibilities are limited. For instance, in
%  operating systems without separate address spaces, like Windows 3.1,
%  we cannot guard against system crashes or similar dangers. If an
%  address space protection is available, for example on workstations,
%  the capabilities of a program to cause damage are limited by the
%  ability to perform system calls (e.g., reading or writing files). By
%  placing an additional agent between the application and the
%  operating system, we can screen offending system calls efficiently.
%  On a specific operating system, Solaris 2.4, this approach has
%  already been realized with only small overhead
%  \cite{UFO96,GoldbergWTB96}.


 The methods discussed so far provide security for the host, using
 user-level methods that do not rely on mechanisms provided by the
 operating system. One can imagine alternative approaches where the
 operating system's mechanisms for authentication, memory protection
 and access control are used (e.g., using \emph{chroot}.)  This approach
 is less flexible since it relies on OS functionality that may not be
 present, or be implemented differently, on various systems. Also, this
 approach is cumbersome, since it requires system administrator
 privileges from the user running the host server software.
 Nevertheless it appears to be a viable alternative for machines used
 as dedicated SuperWeb hosts.


One general concern for the host is whether the implementation of
the method used to provide security can be trusted. For example the current
Java interpreters have not been formally verified for correctness and
therefore a user can not be absolutely certain that the Java interpreter
has no bugs that expose security holes. We recognize that this concern 
will stop certain users from participating in SuperWeb. Nevertheless the
potential danger is apparently perceived as acceptable by the large number
of people who are currently using Java-enabled web browsers on a daily basis.






\subsection{Correctness}

The economic incentive in SuperWeb raises the very real possibility of
incorrect behavior (fraud). To be useful, SuperWeb must provide at
least some mechanism to guarantee correct execution.  How does a
client know that the anonymous host that volunteered to execute a task
produced the correct result?  In an attempt to earn easy cyber-money
the host might have faked a computation and returned a wrong result.
Or, maybe the host had a cheap faulty processor (e.g., an old Pentium)
producing false floating point results.

% A legal aspect of correctness arises when the client feels that the
% host returned a bad result but the host denies it. In general this
% problem very hard to solve. Still, digital signatures can be used to
% verify such claims. Of course using digital signatures implies that
% the broker ascertains the identity of any host or client using some
% authentication mechanism.

% Detecting wrong results is the technical aspect of correctness. 
In some cases it may be easy and computationally cheap for the client to
verify the correctness of the result.  For example, if the task was to
solve a system of linear equations, the client can check that the
result is correct by performing a matrix by vector multiplication
(which is much cheaper than finding the solution). In other cases it is
possible to statistically verify that the result is correct with high
probability.  For example, if the task is to render a 1000x1000 image
using ray-tracing, the client itself can personally compute a few
hundred random pixels of the image and compare them with the
pixels from the image computed by the host.  A more general technique
is for the client (or broker) to insert a checksum computation into
its program; this checksum is returned with the results and checked to
assure that the program was actually run.  Finally the broker or
client can replicate the computation by submitting multiple identical
tasks to independent hosts and comparing the returned results.  This
at least doubles the amount of work done by the computation, but gives
a reasonable guarantee that the results are correct.
Some work in the area of fault-tolerance with {\em malicious}
failures can be found in \cite{YanCW92}.

A related concern is fault-tolerance caused by non-malicious failures:
clients or hosts crash or lose connectivity, networks go down, etc.
This related issue is also important, though easier to handle, and
covered sufficiently in the literature.


%% 
%%  [here is an outline of the big discussion we can make about legal issues.
%%   Do we want that?]
%%   
%%   There is a legal aspect of correctness as well. When the client
%%   detects that the host cheated and produced incorrect results, it
%%   would like to get its cybermoney back. In case the host denies any
%%   wrongdoing the client must be able to prove that the host cheated.
%%   This might be a problem. Evidence is needed: (1) the submitted task
%%   and (2) the returned result. The broker might keep logs of both. But
%%   this is centralized system with a bottleneck. Every communication
%%   between client and host must be logged on broker. We have problem.
%%   A possible solution when a single result from a big computation is
%%   returned is: Client computes a CRC of task and gives it to broker to
%%   log. broker gives task to host. Host verifies CRC and tells broker
%%   CRC is correct. Host computes result and CRC of result. Sends CRC to
%%   broker and result to client. Client verifies CRC of result and tells
%%   broker that it is correct. Broker logs CRC. Now in any dispute about
%%   who sent what both client and host have proof that they really sent
%%   the task they claim the sent or the result they claim they returned.
%%   Still centralized, but small extra load on broker.  Of course, CRC
%%   should actually be some sort of one-way function that cannot be
%%   faked (see digital signatures and public key encryption. No idea
%%   what to do for a distributed computation that uses tons of small
%%   messages.  
%% 
%%   Max's comment: Standard way is to use digital signatures which are
%%   not forgable. if hosts gets signed result, it can use that as
%%   evidence. Same for task+input on the host side.
%%   Requirement her is that host/client now their identity and are not
%%   anonymous. (this can be solved using diffie/hellman public key
%%   exchange).
%%   Broker can also do that, but broker needs extra resources to keep
%%   all results and audit information. So broker wants to charge extra
%%   m\$ for this extra service. 
%% 
%% 
%%   There are several points of failure in our
%%   global computing infrastructure. Both client and host can
%%   crash. Parts of the
%%   Internet may fail disconnecting the client or host from the
%%   broker, or the hosts executing parts of the same distributed
%%   process.  Data may become corrupted on its transition over the network.
%%   These technical aspects of fault-tolerance are well studied.  Error
%%   detection and correction \cite{} can be used to ensure uncorrupted
%%   network communication. The research in fault-tolerant distributed
%%   systems \cite{} \cite{} provides solutions for the design of the
%%   SuperWeb brokers and protocols for interaction between the broker
%%   and the clients and hosts. Other problems such as the
%%   fault-tolerance of parallel task submitted by a client must be
%%   insured by the user designing the task.
%% 
%% Research on fault-tolerant distributed systems with non-malicious failures?
%% 


\subsection{Communication speed}

For many parallel applications the communication network is a
bottleneck. For those applications, a high-performance network is
essential for efficiency.  At present, neither the latency nor the
bandwidth across the Internet are satisfactory.  While emerging
technologies will eventually increase the bandwidth to satisfy any
requirement, the improvement of the latency between
geographically separated computers is limited by the speed of
light.  This severely affects the efficiency of applications requiring
extremely low latency that run globally on our infrastructure.

It seems that for now, only applications that require relatively
little communication will benefit from our \emph{global} computing
infrastructure.  However, the communication capabilities of networks
of workstations (NOW's) or parallel computers can be
exploited. The broker can be instructed to find and map parallel tasks
that require very fast communication to a local NOW or parallel
computer. 

%In another scenario, a cluster of workstations can use a local version
%of SuperWeb. The mini-SuperWeb will only map tasks from local clients
%on local hosts always guaranteeing fast communications.







