and the type B of output data being reduced. Map operation takes individual values of type A and produces, for each a:A a value b:B; Reduce operation requires a binary operation • defined on values of type B; it consists of folding all available b:B to a single value. From basic requirements point of view, any MapReduce operation must involve the ability to arbitrarily regroup data being reduced. Such a requirement amounts to two properties of operation •: associativity: (x • y) • z = x • (y • z) existence of neutral element e such that e • x = x • e = x for every x:B. The second property guarantees that, when parallelized over multiple nodes, the nodes that don't have any data to process would have no impact on the result. These two properties amount to having a Monoid (B, •, e) on values of type B with operation • and with neutral element e. There's no requirements on the values of type A; an arbitrary function A → B can be used for Map operation. This means that we have a Catamorphism A* → (B, •, e). Here A* denotes a Kleene star, also known as the type of lists over A. Shuffle operation per se is not related to the essence of MapReduce; it's needed to distribute calculations over the cloud. It follows from the above that not every binary Reduce operation will work in MapReduce. Here are the counter-examples: building a tree from subtrees: this operation is not associative, and the result will depend on grouping; direct calculation of averages: avg is also not associative (and it has no neutral element); to calculate an average, one needs to calculate moments. Performance considerations MapReduce programs are not guaranteed to be fast. The main benefit of this programming model is to exploit the optimized shuffle operation of the platform, and only having to write the Map and Reduce parts of the program. In practice, the author of a MapReduce program however has to take the shuffle step into consideration; in particular the partition function and the amount of data written by the Map function can have a large impact on the performance and scalability. Additional modules such as the Combiner function can help to reduce the amount of data written to disk, and transmitted over the network. MapReduce applications can achieve sub-linear speedups under specific