here is a brief summary Pregel defines a sequence of supersteps (execution cycles) which are executed in parallel on the entire (partitioned) graph. The super

here is a brief summary Pregel defines a sequence of supersteps (execution cycles) which are executed in parallel on the entire (partitioned) graph. The supersteps are executed by worker threads, synchronized by global synchronization points and coordinated by a master. Pregel keeps vertices and edges on the machine that performs computation and uses network only for message passing. Within a superstep each vertex executes the same user-defined function. There is no message passing between vertices during the superstep but the vertices will recieve their messages in the next cycle only. There are no remote reads, or shared memory concepts like locks, mutexes and semaphores - it is a "pure message passing model". Vertex can modify its state, or that of its outgoing edges, receive messages sent to it in the previous superstep, send messages to other vertices (to be received in the next superstep) or even change the topology of the graph. Vertex state machine has two states Active/Inactive. a vertex is activated by a message received from a previous superstep. A vertex deactivates itself by "voting to halt". When all vertices are deactivated and there are no messages in transit the algorithms terminates. The output of Pregel program is a set of outputs emitted by vertices, could be a directed graph or a set of disconnected vertices or aggregate stats. The authors mention Valiant's "Bulk Syncronous Parallel model" as the main inspiration behind this model (I've found only ACM link: http://portal.acm.org/citation.cfm?id=79181 http://portal.acm.org/citation.cfm?id=79181) ---------------------- PageRank in Pregel: class PageRankVertex : public Vertex<double, void, double> { public: virtual void Compute(MessageIterator* msgs) { if (superstep() >= 1) { double sum = 0; for (; !msgs->Done(); msgs->Next()) sum += msgs->Value(); MutableValue() =0.15 / NumVertices() + 0.85 sum; } if (superstep() < 30) { const int64 n = GetOutEdgeIterator().size(); SendMessageToAllNeighbors(GetValue() / n); } else { VoteToHalt(); } } };