Under consideration for publication in Formal Aspects of Computing Filter-embedding Semiring Fusion for Programming with MapReduce1

We show that MapReduce, the de facto standard for large scale data-intensive parallel programming, can be equipped with a programming theory in calculational form. By integrating the generate-and-test program-ming paradigm and semirings for aggregation of results, we propose a novel parallel programming framework for MapReduce. The framework consists of two important calculation theorems: the shortcut fusion theorem of semiring homomorphisms bridges the gap between specications and efficient implementations, and the lter-embedding theorem helps to develop parallel programs in a systematic and incremental way