Good example for manual execution of MapReduce

Question

I'd like to explain the MapReduce programming model to a group of students. I thought about a little group work, where each student acts as a "Map-process" and has to perform a little computation. The results are then aggregated by other "Reduce" students to gain the overall result.

For comparison, I'd have the best student calculate on his own. In the end, I'd like to compare the time needed for the calculation by the single student and the rest.

The missing part for this group exercise is the type of calculation the students would have to do. Ideally, this would be something which a group can do much faster than a single student. Overall, the computation should not be too complicated and take more than one or two minutes.

I thought about calculating the average temperature over the last 200 years. In this example, 20 "Map" students would calculate the average temperature for a decade, followed by a "Reduce" student calculating the overall average.

I'm not sure if the average temperature calculation is a bit too simple. Are there any calculations which are more suitable for such an exercise?

The students are college students, so their maths levels should be like a high-school graduate.

Answer 1

To craft the problem in a way that you can do it much faster with a group, you need something parallelisable. To give some examples:

• Calculating some aggregate like the average, or maximum.

  To make it simple you could ask them to find the longest word in the first $n$ pages of their math book. It might be an introductory task to let them know what to expect.

• Checking if a number is prime. I doubt this needs additional explanation.

• Sorting, quick-sort is easier, but merge-sort has more involved reduce part.

  For quick-sort you could assign each mapper an interval, and then they are to filter the array and sort it, the reducer would concatenate the arrays in appropriate order.

  For merge-sort you could give each mapper a chunk to sort and then the reducer would merge all the partial results.

• Finding common friends, you can read more about it here.

• Given an array of integers, find the interval of largest sum. To parallelise it, represent any number $x$ as 4-tuple $(x,0,x,0)$ and combine the tuples with

  \begin{align} &(a_1,b_1,c_1,d_1) \otimes (a_2,b_2,c_2,d_2) = \\ &\hspace{20pt}\Big(a_1+a_2, \max(a_1+b_2,b_1), \max(c_1+a_2,c_2), \max(c_1+b_2,d_1,d_2)\Big),\end{align} the result will be the maximum of $c$ and $d$. The above formula is an expanded multiplication of $$\left[\begin{array}{c}a&-\infty&b\\c&0&d\\-\infty&-\infty&0\end{array}\right] \quad\text{starting with}\quad\left[\begin{array}{c}x&-\infty&0\\x&0&0\\-\infty&-\infty&0\end{array}\right]$$ in $(\max,+)$ ring and then reading of the middle of multiplication with $[0,-\infty,0]^T$. You can read more about it here.

I hope this helps $\ddot\smile$