\documentstyle[psbox]{llncs2}
\begin{document}

\title{Towards Bayanihan: Building an Extensible Framework for
Volunteer Computing Using Java}

\author{Luis F. G. Sarmenta,\inst{1}
Satoshi Hirano,\inst{2} 
and Stephen A. Ward\inst{1}}

\institute{MIT Laboratory for Computer Science\\
%545 Technology Square\\
Cambridge, MA 02139, USA\\
{\tt lfgs,ward@cag.lcs.mit.edu}\\
\and
Electrotechnical Laboratory\\
1-1-4 Umezono, Tsukuba, 305, Japan\\
{\tt hirano@etl.go.jp}
 \\
URL: {\tt http://www.cag.lcs.mit.edu/bayanihan}\\
%DRAFT: Dec. 19, 1997
%\thanks{Submitted to the 
%{\em ACM 1998 Workshop on Java for High-Performance Network Computing},
%Palo Alto, California, Feb., 1998}
}

\maketitle

\begin{abstract}
Project Bayanihan seeks to develop the idea of 
{\em volunteer computing\/}, which allows people to very easily pool 
together their computers' 
processing power and cooperate in solving parallel problems.
While the idea of volunteer computing offers many exciting new
prospects in global supercomputing and collaboration, 
its realization involves many challenging research issues 
that need to be addressed.
In this paper, we present a flexible object-oriented framework using 
Java and HORB that allows programmers to experiment 
with different approaches to these issues by simply extending and 
interconnecting basic library components.
We also present results from a distributed web-crawling application
written using the framework.
\end{abstract}

\section{Introduction}

{\em Bayanihan\/} is a Filipino word meaning a community spirit 
of unity and cooperation that makes seemingly impossible tasks
possible through the concerted effort of many people working together
on a common goal.
Project Bayanihan seeks to bring the {\em bayanihan\/} spirit
to global computing by developing the idea of {\em volunteer computing\/}, 
which allows ``ordinary'' people with little technical expertise to 
easily pool together their computers' processing power and cooperate 
in solving parallel problems. 
While the idea of volunteer computing offers many exciting new
prospects in global supercomputing and collaboration, its realization 
involves addressing many challenging issues such as adaptive parallelism,
fault-tolerance, computational security, and scalability \cite{wwca98}.

To address these issues, we have built a software framework using 
Java and HORB \cite{HORB}, a distributed object library similar to 
RMI %\cite{RMI} 
but not requiring JDK 1.1 (which, unfortunately,
is presently not as ubiquitous as JDK 1.0).
By allowing programmers to access remote objects without worrying
about network communication details, HORB allows us to take full advantage
of object-oriented techniques to build an extensible {\em framework}
\cite{Johnson} that lets programmers experiment with different
approaches to research issues by simply filling-in appropriate
{\em hot-spots} in the framework.  

\section{Framework Design}
\label{sec:design}

Figure \ref{fig:system} shows a 
block diagram of a system using the Bayanihan framework.  
\begin{figure}
\centerline{\PSbox{system.ps hoffset=-22 voffset=-618}{11.8cm}{5.6cm}}
\caption{A Bayanihan system}
\label{fig:system}
\end{figure}

On the {\em client} side,
an {\em engine} runs in its own thread, and takes care of receiving
and processing {\em data} objects from its corresponding {\em manager} 
on the server.  
A work engine, for example, would take care of 
getting work data from the work manager, executing the work, and requesting 
more work when it is done.  
Data objects are generally {\em polymorphic}, 
and know how to process themselves.
Work data objects, for example, implement a {\tt doWork()} method,
which the work engine can call.
Both the engine and the data have associated {\em GUI} objects which can
be used for user interface.
The engine and the GUIs are all contained in a {\em chassis} object,
which can be an applet or application.

On the {\em server} side, an {\em advocate} object
serves as the engine's representative, forwarding the engine's 
calls to the manager.
The manager has access to several {\em data pools}, which
may be shared by other managers serving other purposes.  In 
Fig.\,\ref{fig:system}, 
for example, the work and result pools are shared by the work and watch
managers, allowing the watch manager to watch the progress of the
computation and inform watch engines of such things as 
new results and statistics.  
The whole set of associated managers and data pools compose a {\em problem}.  
A problem may include a {\em program} object, which creates and controls 
managers, and data pools, and fills the latter with data objects.
The program may be active (i.e., have its own thread)
or it may be passive, only reacting to occasional callbacks 
from its managers.  
For example, in our current applications, we implement a simple form 
of barrier synchronization by having the work manager do a callback when 
it finishes the current batch of work, and having the program object wait 
for such a callback before creating the next batch of work.
A {\em problem table} keeps track of independent problems on the same server.

Writing an application using the Bayanihan framework typically
involves first selecting and using {\em generic} components 
(shown as shaded boxes in Fig.\,\ref{fig:system}) from a library, 
and 
then defining {\em application-specific} components 
(shown as double-bordered boxes) by extending existing base classes.
In this way, high-level application programmers can write a wide variety of
applications with the same programming model (e.g., master-worker) 
by using a common set of pre-defined engine, manager, and data pool objects,
and then defining different data, GUI, and program objects according to the 
application.

The framework also allows programmers and researchers to
change generic objects in order to implement new functionality.
Researchers, for example, can experiment with performance optimization 
by writing work manager objects with different scheduling algorithms.
Similarly, replication-based fault-tolerance mechanisms can be
implemented by extending the manager and data pool objects.
Programmers can even implement entirely new parallel programming models 
by creating new sets of engines, managers, and data pools.
%For example, one can conceivably implement a PVM-like system \cite{PVM}
%by writing a work engine that functions like a PVM daemon, and
%writing PVM-like tasks as work data objects.  The tasks would
%depend on the engine to provide message-passing and task-spawning
%features, and the engines may depend on the manager for routing, if necessary.

At present, we have implemented a generic set of engines and
managers that support master-worker style programming with
eager scheduling \cite{Charlotte},
and have used it for a variety of demo applications including
factoring, Mandelbrot set rendering, and distributed web-crawling.
We are currently working on extending the basic generic objects to
implement performance, reliability, and programmability improvements.
In the future, we also plan to implement generic components for supporting
Cilk \cite{Cilk} and other adaptively parallel programming models.

\section{An Example: Distributed Web Crawling}
\label{ss:results}

In \cite{wwca98}, we presented the results of a factoring application
which demonstrated the potential use of Java-based volunteer computing 
and the Bayanihan framework for computationally-intensive 
applications.  Here, we present an application
which demonstrates another interesting potential use of
volunteer computing---multiplying not just computational power,
but {\em communication} power as well.

Consider a web crawler (i.e., an application that recursively follows 
links in web pages, compiling a list of pages as it goes along). 
Such an application is extremely communications-bound---i.e., 
most of its time is spent downloading web pages from the network. 
Thus, it can take a long time, even on a fast processor, if network bandwidth 
is limited.
This leads to an interesting idea: what if we can use volunteer computing 
to get {\em other} machines, with their own (possibly faster)
network connections, to do the crawling for us?

To test this idea, we implemented a distributed web-crawling 
application using the Bayanihan framework, and used it in the 
setup shown in Fig.\,\ref{fig:crawler}.  
We simulated a fast computer with a slow network link by placing 
the user 
on a 166 MHz Pentium PC connected to the network through a 28.8Kbps modem.
We ran a Bayanihan server on this machine, and a watcher client
so the user can see the results.
Then, we measured the time it took to find 4000 URLs
starting from {\tt http://www.yahoo.com/},
first running the worker applet on the same PC
(using {\tt appletviewer} with network restrictions turned off), 
and then running it on ``volunteer'' UNIX workstations with slower Java 
interpreters (i.e., the factoring demo runs about 4 times slower on these 
machines) but faster network links (i.e., 10Mbps Ethernet).
\begin{figure}
\centerline{\PSbox{crawler.ps hoffset=-22 voffset=-654}{9.2cm}{4.3cm}}
\caption{The distributed web-crawler experiment.}
\label{fig:crawler}
\end{figure}

Table\,\ref{tab:crawler} shows the results of the experiment
%, with equivalent speeds and relative speedups, 
using two versions of the
application.  The first version was based on the same
``basic'' work engine and work manager objects used in the factoring demo.
Although this version produced the desired speedups, we noticed that its
full potential was supressed by a communications bottleneck---although the 
workers were able to download web pages very quickly through their Ethernet 
links, they were slowed down considerably by the need to report results 
back to the server (on the other side of the modem link) 
for {\em each} work packet before working on the next packet.
To remove this bottleneck, we extended the basic work engine 
and work manager objects to allow the worker to prefetch several packets
of work so that it can do new work while simultaneously reporting 
the results of previously done work.  As Table\,\ref{tab:crawler} shows,
this resulted in up to 80\% more speedup over the basic version.
Furthermore, the new ``multi-work'' versions of the work engine and
work manager can be used transparently in place of the basic version,
allowing us to improve the performance of other applications as well
without the need for recoding.
\begin{table}
\caption{Timing Measurements for the distributed web-crawler.}
%\vspace{2pt}
\centerline{\begin{tabular}{l|r|rrr|rrrr}
\hline
			&	& \multicolumn{6}{c}{UNIX-Ethernet} \\
			&	& \multicolumn{3}{c}{Basic} & \multicolumn{3}{c}{Multi-Work} \\
\hline
measurement 			& PC-mdm & 1 	& 2 	& 3 	& 1	& 2	& 3 \\
\hline\rule{0pt}{12pt}%
time for 4000 URLs (s) 		& 817 	& 391 	& 268 	& 213	& 222	& 148	& 166 \\
speed (URL/s)			& 4.89 	& 10.2 	& 14.9 	& 18.8 	& 18.0	& 27.0	& 24.1 \\
speedup (rel. to PC-mdm) 	& 1 	& 2.09 	& 3.05	& 3.84	& 3.68	& 5.52	& 4.93 \\
speedup (rel. to 1-UNIX)       	&	& 1	& 1.46	& 1.84	& 1	& 1.50	& 1.34 \\
speedup (rel. to Basic) 	&	& 	& 	& 	& 1.76	& 1.81	& 1.28 \\
\hline
\end{tabular}}
\label{tab:crawler}
\end{table}

\section{Related, Present, and Future Work}
\label{sec:relwork}

Project Bayanihan joins a growing number of other projects 
enabling people to use Java for web-based parallel computing.
Most early projects such as ATLAS, ParaWeb, JPVM, and many newer 
projects such as IceT and others presented or referred to in \cite{Java97} 
use Java {\em applications}.  These are more powerful and versatile 
than applets, but require some technical expertise and setup effort from 
volunteer users.  Projects like Bayanihan that support the
use of {\em applets} and Web browsers to allow ``ordinary'' users to 
volunteer their computers seem to be fewer, but have also been growing 
in number.  These include simple systems such as 
%the University of Washington factoring applet \cite{UWFactor}, 
DAMPP \cite{DAMPP}, and more complex and general-purpose 
{\em frameworks} such as Charlotte \cite{Charlotte}, 
and Javelin \cite{Javelin}.
Many of these projects provide the programmer with a way
to easily generate different applications,   
but are usually restricted to following a particular programming model.  

Project Bayanihan takes advantage of the flexibility
and ease-of-use provided by distributed object technology
to build a general-purpose framework for implementing and 
experimenting not only with different applications, but 
with different programming models and volunteer computing 
mechanisms as well.  
Work remains to be done on implementing more complex
programming models, but current results with master-worker 
style applications demonstrate the framework's future potentials.

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

%% This defines the bibliography file (main.bib) and the bibliography style.
%% If you want to create a bibliography file by hand, change the contents of
%% this file to a `thebibliography' environment.  For more information 
%% see section 4.3 of the LaTeX manual.
\begin{thebibliography}{99}

\bibitem{wwca98} L. F. G. Sarmenta.  ``Bayanihan: Web-Based
Volunteer Computing Using Java,''  
{\em Worldwide Computing and Its Applications - WWCA'98},
Springer Lecture Notes in Computer Science 1368, 1998.
{\tt http://www.cag.lcs.mit.edu/bayanihan}

\bibitem{HORB} 
S. Hirano.  ``Distributed Execution of Java Programs,''
{\em Worldwide Computing and Its Applications}, 
Springer Lecture Notes in Computer Science 1274, 1997.%  pp. 29-42. 

\bibitem{Johnson}
D. Roberts and R. Johnson.
``Evolving Frameworks: A Pattern Language for Developing Object-Oriented
Frameworks,''  University of Illinois, 1997.
\\{\tt http://st-www.cs.uiuc.edu/users/droberts/evolve.html}

\bibitem{Charlotte}
A. Baratloo, M. Karaul, Z. Kedem, and P. Wyckoff. 
``Charlotte: Metacomputing on the Web,''
{\em Proc. of the 9th 
International Conference on Parallel and
Distributed Computing Systems}, Sept. 1996.
{\tt http://cs.nyu.edu/milan/charlotte/}

\bibitem{Cilk} R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul,
C. E. Leiserson, K. H. Randall, and Y. Zhou.
``Cilk: An Efficient Multithreaded
Runtime System,'' in {\em Proceedings of the 5th ACM SIGPLAN
Symposium on Principles of Parallel Programming}, July, 1995,
Santa Barbara, California. 
{\tt http://theory.lcs.mit.edu/\~{}cilk/}

\bibitem{Java97}
{\em ACM 1997 Workshop on Java for Science and Engineering Computation}.
Las Vegas, June 1997.
{\tt http://www.npac.syr.edu/users/gcf/03/javaforcse/\\
acmspecissue/latestpapers.html}

\bibitem{DAMPP}
L. Vanhelsuwe. 
``Create your own supercomputer with Java,''
{\em JavaWorld},
Jan. 1997.
{\tt http://www.javaworld.com/jw-01-1997/jw-01-dampp.ibd.html}

\bibitem{Javelin}
{P. Cappello, B. O. Christiansen, M. F. Ionescu, M. O. Neary, 
K. E. Schauser, and D. Wu}.  
``Javelin: Internet-Based Parallel Computing Using Java,''  
{\em ACM Workshop on Java for Science and Engineering Computation}.
Las Vegas, June 1997.  

%\bibitem{SuperWeb}
%{A. D. Alexandrov, M. Ibel, K. E. Schauser, and C. J. Scheiman}.  
%{SuperWeb: Research Issues in Java-based Global Computing.}
%{\em Concurrency: Practice and Experience}.  Vol 9(6). June 1997.
%pp. 535-553. 

%\bibitem{ATLAS} J. Eric Baldeschwieler, Robert D. Blumofe,
%and Eric A. Brewer. ATLAS: An Infrastructure for Global Computing,
%in {\em Proceedings of the Seventh ACM SIGOPS
%European Workshop: Systems Support for Worldwide Applications},
%Sept. 1996.

%\bibitem{Cilk-NOW}
%Robert D. Blumofe, and Philip A. Lisiecki.
%Adaptive and Reliable Parallel Computing on Networks of Workstations.
%In {\em Proceedings of the USENIX 1997 Annual Technical Symposium},
%Anaheim, California, January 6-10, 1997.

%\bibitem{ParaWeb} Tim Brecht, et al.  ParaWeb: Towards World-Wide
%Supercomputing,
%in {\em Proceedings of the Seventh ACM SIGOPS
%European Workshop: Systems Support for Worldwide Applications},
%Sept. 1996.

%\bibitem{Linda}
%Nicholas Carriero and David Gelernter.
%Linda in context.
%{\em Communications of the ACM}, 32(4):444-458, April 1989.

%\bibitem{Chen}
%M. Chen and J. Cowie. Java's Role in Distributed Collaboration.
%{\em Concurrency: Practice and Experience}.  Vol 9(6). June 1997.
%pp. 509-519.
 
%\bibitem{ConcJava97}
%{\em Concurrency: Practice and Experience}.  Vol 9(6). 
%%John Wiley \& Sons, Ltd., 
%June 1997.

%\bibitem{CoreJava}
%Gary Cornell and Cay S. Horstmann. {\em Core Java}, 1ed. 
%Sunsoft Press, Prentice Hall, 1996. 

%\bibitem{djgpp} DJ Delorie.  djgpp Home Page.  
%{\tt http://www.delorie.com/djgpp}

%\bibitem{JPVM} Adam Ferrari.  JPVM: The Java Parallel Virtual Machine.
%June 1996.\\
%{\tt http://www.cs.virginia.edu/\~{}ajf2j/jpvm.html}

%\bibitem{PVM} Al Geist et al. 
%{\em PVM: Parallel Virtual Machine: A User's Guide and 
%Tutorial for Networked Parallelism}.
%{MIT Press},
%{1994}.
%{\tt http://www.netlib.org/pvm3/book/pvm-book.html}

%\bibitem{Piranha}
%David Gelernter and David Kaminsky.
%Supercomputing out of recycled garbage: Preliminary experience
%with Piranha.  In {\em Proceedings of the 1992 ACM
%International Conference of Supercomputing}, pages 417-427,
%Washington, D.C., July 1992.

%\bibitem{IceT}
%Paul A. Gray and Vaidy S. Sunderam.
%IceT: Distributed Computing and Java.
%in {\em ACM 1997 Workshop on Java for Science and Engineering Computation}.
%Las Vegas, June 1997.
%{\tt http://www.npac.syr.edu/users/gcf/03/javaforcse/\\
%acmspecissue/latestpapers.html}

%\bibitem{WWWinda}
%Y. S. Gutfreund.  The WWWinda Orchestrator. \\
%{\tt http://info.gte.com/ftp/circus/Orchestrator}

%\bibitem{HORBJW}
%Junzo Hagimoto.  Construct Java applications
%through distributed object technology.  {\em JavaWorld}, Dec. 1997.\\
%{\tt http://www.javaworld.com/javaworld/jw-12-1997/jw-12-horb.html}


%\bibitem{HORBspeed}
%Satoshi Hirano, Yoshiji Yasu, and Hirotaka Igarashi.  
%Performance Evaluation of Popular Distributed Object Technologies for Java.
%{\em ACM 1998 Workshop on Java for High-Performance Network Computing}, 
%Palo Alto, California, Feb. 1998.

%\bibitem{Lynch} Nancy A. Lynch.  {\em Distributed Algorithms}.
%Morgan Kauffman Publishers, Inc., 1996.


%\bibitem{Jada}
%Davide Rossi.  Jada home page.
%{\tt http://www.cs.unibo.it/~rossi/jada/}


%\bibitem{RMI}
%{{Sun Microsystems, Inc.}}
%{Remote Method Invocation}.\\
%{\tt http://www.javasoft.com/products/jdk/1.1/docs/guide/rmi/}


%\bibitem{UWFactor} Geoff Voelker and Dylan McNamee.  The Java
%Factoring Project.  HTML document with Java Alpha version applets,
%Sept. 1995.\\
%{\tt http://www.cs.washington.edu/homes/dylan/ContestEntry.html}

\end{thebibliography}


\end{document}







