  MapReduce is a commonly used framework for executing data-intensive jobs on
distributed server clusters. We introduce a variant implementation of
MapReduce, namely "Coded MapReduce", to substantially reduce the inter-server
communication load for the shuffling phase of MapReduce, and thus accelerating
its execution. The proposed Coded MapReduce exploits the repetitive mapping of
data blocks at different servers to create coding opportunities in the
shuffling phase to exchange (key,value) pairs among servers much more
efficiently. We demonstrate that Coded MapReduce can cut down the total
inter-server communication load by a multiplicative factor that grows linearly
with the number of servers in the system and it achieves the minimum
communication load within a constant multiplicative factor. We also analyze the
tradeoff between the "computation load" and the "communication load" of Coded
MapReduce.
