The Popcorn Project
Globally Distributed Computation Over the Internet
Noam Nisan
Hebrew University, Jerusalem
and
Interdisciplinary Center, Herzliya
Shmulik London, Ori Regev, Noam Camiel
Hebrew University, Jerusalem
http://www.cs.huji.ac.il/~popcorn
Idea

Millions of computers connected to the internet

“Safe” programming languages (java) allow these
computers to securely execute remote code
Use all of these computers as a single huge parallel
machine
Global vs. Distributed

Technical difficulties
code mobility, security

“More distributed”
communication, reliability, number / type of
processors

Different owners
payment / negotiation, verification, getting in touch
Related Work

Network of workstations (Berkeley NoW, …)

Special purpose efforts (factoring by web [Lenstra])

Java applet-based examples (javaworld article)

Other global systems:

The legion project

Charlotte

Paraweb (Brecht, Sandhu, Shan, Talbot)

Superweb (Alexandrov, Ibel, Schauser, Sceiman)
(university of Virginia)
(Baratloo, Karaul, Kedem, Wyckoff)
Rest of Talk





System overview
Programming paradigm
Applications
Market mechanisms
Ongoing and future research
Popcorn Architecture
Buyer
Computelets
Seller
Market
Seller
Buyer
Seller
The Seller’s Point of View
Programming Paradigm -- Requirements
Coarse grained
 Distinction: central vs. remote
 Unknown number and type of processors
 Communication is expensive
 Well-encapsulated sub-computations (payment,
verification, re-computation…)

Programming Paradigm -- Overview
Main program repeatedly generates computation-packets
for remote execution and handles the results.
•Code
•Verification
•Data
•Payment
•Handle result
Computelet
Computation Packet
Computelet vs. RMI
Asynchronous
 Local source of code
 Server anonymity
 Data is part of object

(Very restricted software agent)
Findmax Example
import popcorn.*;
public class FindMaxPacket extends ComputationPacket {
static int maxarg = 0;
public static void main(String[] args) {
for (int a=0; a < 10000; a+=100)
new FindMaxPacket(a,a+99).go();
collectAll();
System.out.println(maxarg);
}
public FindMaxPacket(int from, int till) {
super(FindMaxComputelet(from,till));
}
public void completed() {
update((Integer)getResult().intValue());
}
static synchronized void update(int candidate){
maxarg = (FindMaxComputelet.g(candidate) >
FindMaxComputelet.g(maxarg)) ? candidate : maxarg;
}
}
Findmax Example (cont.)
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 . . .
}
}
Verification
Multiple copies of each computelet
 Spot-checks
 NP-type proofs
 Program checking/correcting
 Hidden partial knowledge of answer


Best: auto-robust programs
Candidate Applications

Combinatorial search

Optimization problems

Code breaking

Internet search

Games

Planning
Example: Simulated Annealing
( Metropolis, Genetic Algs, Hill-Climbing, Branch-n-Bound…)
Sequential version:
x <- initial solution
( maybe random, maybe many x’s )
repeat
x <- some “neighbor” of x
( usually “better”, maybe random)
until
solution seems good
Popcorn Parallel Version
Chose S = set of initial solutions
Repeat
Get some x in S
Remotely improve(x)
When improve(x) returns, update(S)
To improve(x)
repeat k times
x <- some nbr of x
return [x] (or l best solutions)
Traveling-salesman Example
(Shmulik London & Rivki Spira)
Trade in CPU Time
Popcoin accounts
 Pricing:

Per JOP (auto benchmark) or per computelet

Buyer:
API for setting contract or use GUI tool

Seller:
Payment in popcoins or get information
The Popcorn Logo
Buyer
CPU time
Popcoins
Seller
Information
Publisher
Market Mechanisms

Vickrey auction
Buyer: offers price
Seller: no input

Double auction
Buyer: low, high, rate
Seller: high, low, rate
(Granularity: computelet/contract)
Implementation
http://www.cs.huji.ac.il/~popcorn
System operational, 30Kloc (pure Java 1.1)
 Test-bed for further research
 Online market, developer download
 Small scale testing
 A few applications
 Throughput: ~5 packets/sec (interpreted, monitored,

200mhz PC)
Current Work
Scalability: A network of markets
 Scalability: tree of computelets
 Tightly coupled variant: shared objects
 Market analysis
 Verification support
 Tools / languages
 Applications

Higher Level Issues

Other resources:
 Space (disk, memory)
 Communication (routing, bandwidth)
 Information (DBs, multimedia)
 Algorithms

Electronic markets:
 Mechanisms
 Payments
 Implementation
Descargar

Popcorn (Paradime Of Parallel Computation Over Remote