Coded MapReduce

By Songze Li, Mohammad Ali Maddah-Ali, Amir Salman Avestimehr. 2015

173 citations recorded by the source corpus.

MapReduce is a commonly used framework for executing data-intensive tasks on distributed server clusters. We present “Coded MapReduce”, a new framework that enables and exploits a particular form of coding to significantly reduce the inter-server communication load of MapReduce. In particular, Coded MapReduce exploits the repetitive mapping of data blocks at different servers to create coded multicasting opportunities in the shuffling phase, cutting down the total communication load by a multiplicative factor that grows linearly with the number of servers in the cluster. We also analyze the tradeoff between the “computation load” and the “communication load” of the Coded MapReduce.

Subfields: Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Speeding Up Distributed Machine Learning Using Codes (2015, background): “[71] proposed coded MapReduce that reduces the communication cost in the process of transferring the results of mappers to reducers.”
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy (2018, background): “coded computing) was initiated in [17], [18], [20].”
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (2017, background): “As a by-product, we can also prove that the polynomial code simultaneously achieves optimality in terms of several other performance metrics, including the computation latency [5, 10], the probability of failure given a deadline [9], and the communication load [16, 17, 18], as discussed in Section 3”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, methodology): “In [19], coding was used to speed up MapReduce [20], a commonly used framework for distributing and shuffling data while executing data-intensive tasks on distributed clusters.”
Communication-Computation Efficient Gradient Coding (2018, methodology): “The communication in our problem is from all the worker nodes to one master node, while the communication in (Li et al., 2015; 2017b) is from all workers to all workers, and there is no master node in (Li et al.”
Gradient Coding (2016, background): “Further closely related work has shown how coding can be used for distributed MapReduce, as well as a similar communication and computation tradeoﬀ (Li et al., 2015, 2016b).”
Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, background): “In [13], [14], for a general MapReduce framework implemented on a distributed computing cluster, an optimal tradeoff between the local computation on individual workers and the communication between workers was characterized, exploiting coded multicasting opportunities created by carefully designing”
Wireless Edge Computing With Latency and Reliability Guarantees (2019, methodology): “Sec. 4.1.2) low propagation delay proximity based computing deep reinforcement learning based task ofﬂoading (Sec. 4.2, use case 4) computing power, task dependency parallel and coded computing [50], [51] low propagation delay, energy efﬁciency proactive computing use case 6 in Sec. 4.2 low predicti”
Coded computation over heterogeneous clusters (2017, background): “The first coding concept introduced in [5], [6] enables an inverse-linear tradeoff between computation load and communication load in distributed computing.”
Gradient Coding From Cyclic MDS Codes and Expander Graphs (2017, background): “Further closely related work has shown how coding can be used for distributed MapReduce, as well as a similar communication and computation tradeoff [16], [18].”
Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding (2018, background): “There has recently been an exciting surge of coding-theoretic strategies to mitigate straggler and bandwidth bottlenecks (see, e.g., [8]–[15]).”
Gradient Coding: Avoiding Stragglers in Distributed Learning (2017, background): “Further closely related work showed how coding can be used for distributed MapReduce and how to trade off communication and computation (Li et al., 2015), (Li et al.”
Coded TeraSort (2017, methodology): “In the general CMR scheme proposed in [7], [9], the computation of each Map task is repeated at r carefully chosen nodes (i.e., incurring computation load of r ), in order to enable the nodes to exchange coded multicast messages that are simultaneously useful for r other nodes.”
A Fundamental Tradeoff Between Computation and Communication in Distributed Computing (2016, methodology): “We index these subsets as S(k)[1],S(k)[2] .”
Coded Computation Over Heterogeneous Clusters (2019, background): “The first coding concept introduced in [6]–[8] enables an inverse-linear tradeoff between computation load and communication load in distributed computing.”