The POPCORN system [1], under development in the Hebrew University of Jerusalem, is aimed at providing a global, Internet-wide, distributed virtual computer. In principal, all the millions of processors connected to the Internet at any given moment can serve as part of a single huge parallel virtual machine. Towards this goal we provide an infrastructure for programming distributed computations in Java using our libraries, and executed using all processors on the Internet which care to participate. Market incentives for such participation are also supported by the system.
In the context of a single local network, this idea has been successfully attempted by rather many systems by now, especially due to the influence of the work done in "Network of Workstations" (NoW)[2]. However, the situation is more complicated when it comes to the whole Internet. Several technical difficulties immediately come to mind: the operating systems of remote computers can not be changed, as is often done in NoWs; code must be dynamically transferred to remote machines with unknown hardware and software; the remote machines should be secured from malicious code, etc.
Any general framework for global computation would thus require mechanisms for "mobile-code" providing code mobility as well as security over the Internet. Indeed, until recently such general global systems were not feasible, and only special-purpose computations have been done globally [3]. The recent wide availability of the Java language [4] with its virtual machine embedded in popular browsers and its security mechanisms finally allows such "global" systems to be built. The POPCORN system is built on top of Java, and thus allows cooperation of all Java-enabled computers on the Internet -- in a safe and simple manner (and totally in user-space). We know of several other on-going projects which utilize Java towards similar goals [6,7,8].
Even after the basic code mobility and safety problems are resolved, there are still some very fundamental differences between global computing systems (such as those POPCORN aims at) and local distributed systems (such as NoWs). The first difference is a matter of scale: The Internet is much more "distributed": The communication bandwidth is smaller, the latency higher, the reliability lower. Processors come and go with no warning and no way to control them. On the positive side, the potential number of processors is huge. We believe that while the Internet currently cannot hope to serve as a totally general purpose efficient parallel computer, it can still provide excellent computational resources for a wide variety of computational problems. In particular, we feel that many optimization problems and techniques (e.g. brute-force search, hill climbing, simulated annealing, genetic algorithms, branch-and-bound, etc.) can be efficiently implemented over the Internet.
A more interesting difference is due to the distributed ownership of the processors on the Internet. Since each processor is owned and operated by a different person or organization, there is no a-priori motivation for cooperation (why should my computer work on your problem?). Clearly a motivation for cooperation must be provided by a global computing system. In addition processors on the Internet may be malicious or faulty, and thus can not necessarily be trusted.
There are three distinct entities in the POPCORN system:
A POPCORN computation is normally composed of a single thread of execution running on the local machine. This thread may send off well defined sub-computations for remote execution. A computelet abstracts this sub-computation, including the code to be executed as well as the data needed. Each invoked computelet is synchronously executed remotely, and the local thread of computation is informed when the answer arrives. There is a semantic difference between computelets and usual RMI: the invoking program does not care or specify where the computelet actually gets executed, while the remote machine may execute any computelet since its code originates from the caller.
While this notion of computelets is weaker than general shared-memory or message passing parallel programming notions, we believe that it fits well global computation. The main advantage is that by encapsulating a well defined part of the parallel program as a computelet, we have great control over its usage, price, resource use, etc. We can verify its results, re-send it if needed, pay for it, etc. In global computation where parts of the computation may get lost, be incorrect, require payment, etc., this well-defined control becomes important.
Selling CPU-time is extremely easy: you visit the web-page of our market with a Java-1.1-enabled browser (we use the Java 1.1 serialization package in our implementation hence the need for Java 1.1). A seller may quit the computation at any given moment by leaving the web-page, losing the current executing computelet, but keeping all earnings for previous computelets. At this web-page the seller can choose between two options for getting paid. The first possibility is to play one of the simple games we provide, with the knowledge that while the game is being played the CPU will also be used in the background for executing computelets. This possibility does not add popcoins to the seller's account as his payment is the game itself.
The second possibility a seller has is to get paid in popcoins. For this possibility, the seller enters the popcoin-account ID to which the popcoins should be deposited. The market guarantees that the highest paying available computelet will be sent to the current sellers at any given moment -- thus maximizing the sellers' profits. The popcoins earned this way have no value outside of the POPCORN system, but may later be used inside the POPCORN system for buying CPU-time in future parallel programs. In addition, popcoins can be used for "buying" some (silly) information we provide or for playing some simple games we provide.
A buyer of CPU-time must have previously established an account in the market. As long as he keeps a positive popcoin balance, new computelets may be sent for remote execution. Each computelet is sent to the market with a price-tag set by the buyer. This price-tag may be in one of two forms. In the first form the buyer declares how many popcoins he is willing to offer for the execution of the whole computelet. When the computelet's answer is sent to him this amount is deducted from his popcoin account. In the second variant the buyer declares how many popcoins he is willing to offer for each unit of computation in the computelet. The amount of units of computation actually taken by the computelet is transparently approximated by POPCORN using a simple benchmark which it runs in the background on the sellers' processor while the computelet runs.
The only motivation for offering a high price for a computelet is that higher
paying computelets get priority over lower paying ones. Thus if your offer is
too low, your computelet may never get executed since more recent yet higher paying
computelets may take up all available CPU-time. To allow the buyer more control
over the price, we supply a mechanism by which the buyer may instruct the market
to automatically increase the price at a given rate until sellers can be found.
Technically, in the simplest form, a POPCORN programmer is expected to subclass the two basic classes: popcorn.ComputationPacket and popcorn.Computelet. In the Computelet subclass he overrides the Computelet.compute() method with the code to be executed remotely. In the ComputationPacket subclass he overrides the ComputationPacket.completed() method with the code which handles the results when they arrive. In addition a main program is written which generates the computation packets needed for the whole computation. Below we list an example of a complete POPCORN program which finds the maximum of a function using simple brute force search of all possibilities. Notice that no verification of the remote computations is attempted in this program, yet incorrect results do not completely destroy the computation but rather can only result in suboptimality of the solution.
import popcorn.*;
public class FindMaxPacket extends ComputationPacket {
static int maxarg;
public static void main(String[] args) {
maxarg=0;
for (int a=0; a < 10000; a+=100)
new FindMaxPacket(a,a+99).go();
collectAll();
System.out.println("maxarg(g(x))="+maxarg);
}
public FindMaxPacket(int from, int till) {
super(FindMaxComputelet(from,till));
this.setContract(new StandardBuyerContract(
new FixedPopcoinPacketBid(10.0));
}
public void completed() {
update((Integer)result().intValue());
}
static synchronized void update(int candidate) {
maxarg = (FindMaxComputelet.g(candidate) >
FindMaxComputelet.g(maxarg)) ?
candidate : maxarg;
}
}
class FindMaxComputelet implements Computelet {
private int from,till;
public FindMaxComputelet(int from, int till){
this.from=from;
this.till=till;
}
public Object compute() {
int maxarg=from;
for (int x=from; x<=till; x++)
maxarg = (g(x)>g(maxarg)) ? x : maxarg;
return new Integer(maxarg);
}
// the function we want to maximize
public static int g(int x) {
return . . .
}
}
|
[2] Network of Workstations. Patterson et al. http://now.cs.berkeley.edu
[3] Factoring by Web. Lenstra. http://www.npac.syr.edu/factoring/info.html
[4] JavaSoft home page. http://www.javasoft.com
[5] RMI http://chatsubo.javasoft.com/current/index.html
[6] ParaWeb: Towards World-wide Supercomputing http://villi.cs.yorku.ca/reports/paraweb/Welcome.html
[7] SuperWeb: Towards a Global Web-Based Parallel Computing Infrastructure / Albert D. Alexandrov, Maximilian Ibel, Klaus E. Schauser, Chris J. Scheiman. Manuscript.
[8] A. Baratloo, M. Karaul, Z. Kedem, and P. Wyckoff. Charlotte: Metacomputing on the Web. In Proceedings of 9th Conference on Parallel and Distributed Computing System, 1996.
[9] Blum M., Luby M., Rubinfeld R.,
"Self-Testing/Correcting with Application to Numerical Problems", STOC 1990.