Module 8b - Graph Processing

Question 1

What is the motivation for Google Pregel?

Answer 1

• Many important data sets look like graphs.

- Some graph sets are massive, and computations can be parallelized

Question 2

A Pregel computation consists of a sequence of iterations called a superstep.

What are the 6 things that occur during a superstep?

Answer 2

1. Workers asynchronously execute a user-defined function on each vertex
2. Vertices can receive messages sent in the previous superstep
3. Vertices can modify their value, modify the values of their edges, as well as add/remove edges
4. Vertices can send messages to be received in the next superstep
5. Each vertex may also deactivate itself (i.e., vote to halt)
6. An inactive vertex is reactivated when it receives a message

Question 3

The model of computation in pregel is vertex-centric. What does this mean?

Answer 3

“think like a vertex”

Question 4

During a superstep in pregel, what can a vertex do?

Answer 4

• A vertex can read messages sent to it in superstep S − 1,
• A vertex can send messages to other vertices that will be received at superstep S + 1
• A vertex can modify the state of V and its outgoing edges.

Question 5

What does pregel maintain in the state for each vertex?

Answer 5

1. A problem specific value (ex: PageRank value)
2. A list of messages sent to the vertex
3. A list of outgoing edges
4. A binary active/inactive state

Question 6

In pregel, supersteps are computed _______, whereas workers compute _______ within each superstep, and communicate in _______ supersteps

Answer 6

synchronously
asynchronously
between

Question 7

What is a vertex partition in Pregel?

Answer 7

A subset of a directed graph’s vertices. Each worker is responsible for a vertex partition

Question 8

In Pregel, vertices can be either “active” or “inactive”.

How does a vertex switch from active to inactive? vice versa?

Answer 8

• If an active vertex votes to halt, then it becomes inactive
• If an inactive vertex receives a message, then it becomes active

Question 9

When does the pregel program stop executing?

Answer 9

A distributed execution stops when all vertices are inactive and where are no more messages to process

Question 10

Do computing units (vertices) in Pregel use shared memory?

Answer 10

No. They use message passing. Each vertex uses message passing to communicate with other vertices

Question 11

Upon initialization of a Pregel program, how is vertex ownership determined?

Answer 11

• The vertex ownership is determined by a partitioner, which by default is a simple hash function over vertices.
• This ensures a fairly even distribution of data across workers, but does not always balance the computation

Question 12

In Pregel, what does a worker do upon initialization?

Answer 12

• Each worker reads its section of the input
• Stores vertices that belong to it
• Forwards the remaining vertices to the appropriate workers

Question 13

In Pregel, what does the master do upon initialization?

Answer 13

• Assigns a section of the input to each worker, (similarly to the way input splits are determined in Hadoop)

Question 14

Upon initialization of the Pregel program, can the user override the default partitioning scheme?

Answer 14

Yes, it can be overwritten to exploit locality by co-locating graph components or dense subgraphs

Question 15

In Pregel, combiners are supported (similar to Hadoop).

What is the benefit of combiners in Pregel? What is the drawback?

Answer 15

• Combiners reduce the amount of data exchanged over the network and the number of messages
• This trades CPI cycles against network I/O

Question 16

In Pregel, for what cases are combiners applicable?

How are combiners enabled?

Answer 16

Combiners are applicable for when the function applied at each vertex is communicative and associative (ex: min, max, sum)

Combiners are user-defined and explicitly enabled

Question 17

In Pregel, aggregators are supported.

What do aggregators do? What can they be used for?

Answer 17

• Aggregators are used to compute aggregate statistics from vertex-reported values
• Aggregators can be used to evaluate a convergence criterion in an iterative computation

Question 18

In Pregel, aggregators are supported.

Explain the mechanism for workers and masters using aggregators in between supersteps

Answer 18

• Workers aggregate values from their vertices during each superstep
• At the end of each superstep, the values from the workers are aggregated in a tree structure, and the value from the root of the tree is sent to the master
• The master shares the value with all vertices in the next superstep

Question 19

As a part of fault tolerance in pregel systems, what does the master do at the start of a superstep?

How is the frequency of these operations determined?

Answer 19

For fault tolerance, at the start of a superstep:
- The master tells the workers to save their state to a persistent storage. Just like a checkpoint

• This includes vertex values, edge values, and list of incoming messages
• The master also saves any aggregator values
• The frequency of these operations is user-determined

Question 20

Fault tolerance in Pregel systems. What happens when the master detects one or more worker failures?

Answer 20

When the master detects a failure:

• Rolls back all workers to the most recent checkpoint
• Computation is repeated from this checkpoint

Question 21

In a Pregel system, what how can the fault tolerance be made more effiicient?

Answer 21

A more efficient recovery system:

• Only the failed workers revert to the checkpoint
• This requires deterministic replay of any messages sent to those workers at each superstep since the checkpoint

Question 22

Pregel is a model for ______ distributed _____ computation

Answer 22

scalable

graph