[null, null, {"document_url": "http://grigory.us/blog/mapreduce-model/", "unformatted_src": "http://grigory.github.io/blog/pics/cluster.png", "src": "http://grigory.github.io/blog/pics/cluster.png", "formatted_filename": "cluster", "alt_text": "MapReduce cluster"}, null, null, {"document_url": "http://grigory.us/blog/mapreduce-model/", "unformatted_src": "http://grigory.github.io/blog/pics/mr-storage.png", "src": "http://grigory.github.io/blog/pics/mr-storage.png", "formatted_filename": "mr storage", "alt_text": "MapReduce Storage"}, null, {"document_url": "http://grigory.us/blog/mapreduce-model/", "unformatted_src": "http://grigory.github.io/blog/pics/mr-computation-diagram.png", "src": "http://grigory.github.io/blog/pics/mr-computation-diagram.png", "formatted_filename": "mr computation diagram", "alt_text": "MapReduce Computation Diagram"}, null, {"document_url": "http://grigory.us/blog/mapreduce-model/", "unformatted_src": "http://grigory.github.io/blog/pics/rounds.png", "src": "http://grigory.github.io/blog/pics/rounds.png", "formatted_filename": "rounds"}, null, {"document_url": "http://grigory.us/blog/mapreduce-model/", "unformatted_src": "http://grigory.github.io/blog/pics/connectivity.png", "src": "http://grigory.github.io/blog/pics/connectivity.png", "formatted_filename": "connectivity", "alt_text": "Connectivity"}, null]
The Big Data Theory Grigory Yaroslavtsev

Email Twitter Facebook Google+ LinkedIn Github

Model for Massively Parallel Computation

In this post I will introduce a theoretical model for computation in centralized distributed massively parallel computational systems (or in short clusters like those used by Google many other companies). Over the last decades the supercomputer architecture has moved towards such designs and there seem to be no signs of this trend slowing (see Wikipedia article for more information). MapReduce-style Computation

MapReduce is a programming model for cluster computing introduced by Jeff Dean and Sanjay Ghemawat in their seminal paper. There exist multiple different implementations of MapReduce, Apache Hadoop being one of the most popular among them. Below I will describe a theoretical version of the model for MapReduce-style computation. This model is easy to understand, avoiding low-level technical details involved in the implementation of the MapReduce model. For those familiar with the standard MapReduce implementations, which use key-value pairs and Map/Shuffle/Reduce phases, let me just say that these two are interchangeable abstractions of the same thing.

This model has emerged in a sequence of papers:

Storage Model

First, let’s discuss the data storage. Data of size is partitioned between identical machines. Each machine is the standard RAM machine with bits of RAM. The data fits into the overall memory with possibly some extra memory left for the algorithm to use so that , where is an overhead replication factor. Unless otherwise specified, replication will be constant, i.e. so I will ignore it.

Without loss of generality I will assume that and . Here is a constant, which is typically significantly greater than zero, but less than (think of a cluster with thousands of machines, each having gigabytes of RAM). Computational Steps

The key parameter in the study of massively parallel algorithms is the number of supersteps (or rounds) of computation. The entire computation is divided into such rounds, each consisting of two phases: Number of Rounds

Overall, if the number of rounds is then the total local computational time is . The total communication time is , where is the time it takes to redistribute the data between machines in each round. This parameter is dependent on the under the hood implementation of the system so I will assume it as given.

For example, if local running times are linear then we get total running time of . This emphasizes the number of rounds as the key parameter for understanding the complexity of algorithms in MapReduce-like systems. Other considertaions, such as fault-tolerance, also suggest that ideally we would like to have just a few rounds. So having rounds is great, while rounds might be also ok for some problems. Let’s look at some examples of how many rounds it takes to solve some basic problems:

In practice it takes two rounds for a terabyte dataset using TeraSort, which uses essentially the same algorithm as the theoretical -round algorithm mentioned above. Here is a simplified version:

The connectivity algorithm is more complex so I will describe it in more detail below.

Connectivity in rounds

The data consists of edges of an undirected graph on the vertex set . The goal is to compute the connected components of this graph. For every vertex let be its unique integer id (a number between and ). During the algorithm we will also maintain a label for each vertex . Let be the set of vertices with the label . During the execution of the algorithm this set will be a subset of the connected component containing . We will use and to denote the set of neighbors of a vertex and a subset of vertices respectively.

Here is a high-level description of the algorithm. I will call some of the vertices active. The idea is that every set of vertices with the same label according to will have exactly one active vertex during the execution of the algorithm.

It is easy to see if for two vertices and it holds that then and are in the same connected component. It remains to show that every connected component will have a unique label with high probability after phases. We will show that for every connected component in the graph the number of active vertices in this component reduces by a constant factor in every phase. Indeed, half of the active vertices in every component is declared as non-leaders. Fix an active non-leader vertex . If there are at least two different labels in the connected component containing then there exists an edge such that and . The vertex is marked as a leader with probability so in expectation half of the active non-leader vertices will change their label in every phase. Overall, we expect of labels to disappear. By a Chernoff bound after phases the number of active labels in every connected component will drop to one with high probability.

Finally, I will leave it as an excercise to check that each phase of the algorithm above can be implemented in constant number of rounds. Indeed, it is not hard to see that selection of leaders, computation of (the smallest label in for active non-leader nodes ) and relabeling can all be done in constant number of rounds.

Open Problem

Is it possible to solve connectivity in constant number of rounds? This is a big open problem in the area and the consensus seems to be that this is not possible. In fact, it is open even whether one can distinguish a cycle on vertices from two cycles on vertices each in constant number of rounds. You might also enjoy (View all posts)
