# Concurrent vs. Exclusive Reading in Parallel Decoding of LZ-Compressed Files +
## 4 The MapReduce Implementation of the CREW Algorithm
### The MapReduce Model of Computation  
The MapReduce model allows global computation on a distributed system in its theoretical formulation. Therefore, bounding the number of computational steps is a requirement for the design of a practical algorithm.  
The MapReduce programming paradigm is a sequence \(P=\mu_{1}\rho_{1}\cdots\mu_{R}\rho_{R}\), where \(\mu_{i}\) is a mapper and \(\rho_{i}\) is a reducer for \(1\leq i\leq R\). First, we describe this paradigm and then discuss how to implement it on a distributed system. Since the input/output phases are inherent to any parallel algorithm and have standard solutions, the sequence \(P\) does not include the I/O phases, and the input to \(\mu_{1}\) is a multiset \(U_{0}\) where each element is a \((key,value)\) pair. The input to each mapper \(\mu_{i}\) is a multiset \(U_{i-1}\) output by the reducer \(\rho_{i-1}\), for \(1<i\leq R\). Mapper \(\mu_{i}\) is run on each pair \((k,v)\) in \(U_{i-1}\), mapping \((k,v)\) to a set of new \((key,value)\) pairs. The input to reducer \(\rho_{i}\) is \(U^{\prime}_{i}\), the union of the sets output by \(\mu_{i}\). For each key \(k\), \(\rho_{i}\) reduces the subset of pairs of \(U^{\prime}_{i}\) with the key component equal to \(k\) to a new set of pairs with key component still equal to \(k\). \(U_{i}\) is the union of these new sets.  
In a distributed system implementation, a key is associated with a processor. All the pairs with a given key are processed by the same node, but more keys can be associated to it in order to lower the scale of the system involved. Mappers are in charge of the data distribution, since they can generate new key values. On the other hand, reducers just process the data stored in the distributed memory, since they output for a set of pairs with a given key another set of pairs with the same given key.  
The following complexity requirements are stated as necessary for a practical interest in [11]:  
* \(R\) is polylogarithmic in the input size \(n\);
* the number of processors (or nodes in the Web) involved is \(\text{O}(n^{1-\epsilon})\) with \(0<\epsilon<1\);
* the amount of memory for each node is \(\text{O}(n^{1-\epsilon})\);
* mappers and reducers take polynomial time in \(n\).  
In [11], it is also shown that a \(t(n)\) time CREW PRAM algorithm using subquadratic work space and a subquadratic number of processors can be implemented by MapReduce with a simulation satisfying the above requirements if \(t(n)\) is polylogarithmic. Indeed, the parameter \(R\) of the simulation is \(\text{O}(t(n))\), while the subquadratic work space is partitioned among a sublinear number of processors taking polynomial computational time.  
Such requirements are necessary but not sufficient to guarantee a speed-up of the computation. Obviously, the total running time of mappers and reducers cannot be higher than the sequential one, and this is trivially implicit in what is stated in [11]. The non-trivial bottleneck is the communication cost of the computational phase. This needs to be checked experimentally, since \(R\) can be polylogarithmic in the input size. Generally speaking, a MapReduce implementation hasa practical interest if \(R\) is about ten units or less. If this is obtained from the simulation of a CREW PRAM algorithm, it might be preferable to the simulation of an EREW PRAM algorithm with a higher number of iterations.