MapReduce

I used to work in parallel (PRAM) algorithms more than a decade ago, and have always been curious how parallelism will work out for real. Now, we have some positive developments. Google for example uses systems such as Sawzall and MapReduce to process large amount of data using 1000's of parallel, loosely synchronized machines. A bunch of us have spent time trying to abstract a computational model for Sawzall and MapReduce. We have made a start with what we call the MUD model. More remains to be done, in particular, with a bounded number of rounds and a large number of "keys". Any new model or algorithmic insight is likely to be useful since these systems are widely used in practice.