popcorn 1

The Popcorn Project: 

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: 

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: 

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: 

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 (university of Virginia) Charlotte (Baratloo, Karaul, Kedem, Wyckoff) Paraweb (Brecht, Sandhu, Shan, Talbot) Superweb (Alexandrov, Ibel, Schauser, Sceiman)

Rest of Talk: 

Rest of Talk System overview Programming paradigm Applications Market mechanisms Ongoing and future research

Popcorn Architecture: 

Popcorn Architecture Market Seller Seller Seller Buyer Buyer Computelets

The Seller’s Point of View: 

The Seller’s Point of View

Programming Paradigm -- Requirements: 

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…)

Slide 9: 

Programming Paradigm -- Overview Main program repeatedly generates computation-packets for remote execution and handles the results. Verification Payment Handle result Code Data Computelet Computation Packet

Computelet vs. RMI: 

Computelet vs. RMI Asynchronous Local source of code Server anonymity Data is part of object (Very restricted software agent)

Findmax Example: 

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.): 

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: 

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: 

Candidate Applications Combinatorial search Optimization problems Code breaking Internet search Games Planning

Example: Simulated Annealing: 

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: 

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: 

Traveling-salesman Example (Shmulik London & Rivki Spira)

Trade in CPU Time: 

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: 

The Popcorn Logo Buyer Seller Publisher CPU time Information Popcoins

Market Mechanisms: 

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: 

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: 

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: 

Higher Level Issues Other resources: Space (disk, memory) Communication (routing, bandwidth) Information (DBs, multimedia) Algorithms Electronic markets: Mechanisms Payments Implementation