## April 9, Spring Quarter 2010: Theory Seminar

### 1:00pm in ICS 243

#
A Model of Computation for MapReduce

## Lowell Trott, University of California, Irvine

Presenting a SODA paper by
Howard Karloff, Siddharth Suri, and Sergei
Vassilvitskii

Abstract:
We compare MapReduce to the PRAM model of
computation. We prove a simulation lemma showing
that a large class of PRAM algorithms can be eciently
simulated via MapReduce. The strength of MapReduce,
however, lies in the fact that it uses both sequential and
parallel computation. We demonstrate how algorithms
can take advantage of this fact to compute an MST of a
dense graph in only two rounds, as opposed to Omega(log(n))
rounds needed in the standard PRAM model. We show
how to evaluate a wide class of functions using the
MapReduce framework. We conclude by applying this
result to show how to compute some basic algorithmic
problems such as undirected s-t connectivity in the
MapReduce framework.