  This work explores fundamental modeling and algorithmic issues arising in the
well-established MapReduce framework. First, we formally specify a
computational model for MapReduce which captures the functional flavor of the
paradigm by allowing for a flexible use of parallelism. Indeed, the model
diverges from a traditional processor-centric view by featuring parameters
which embody only global and local memory constraints, thus favoring a more
data-centric view. Second, we apply the model to the fundamental computation
task of matrix multiplication presenting upper and lower bounds for both dense
and sparse matrix multiplication, which highlight interesting tradeoffs between
space and round complexity. Finally, building on the matrix multiplication
results, we derive further space-round tradeoffs on matrix inversion and
matching.
