Coded MapReduce

Songze Li; Mohammad Ali Maddah-Ali; A. Salman Avestimehr

doi:10.1109/ALLERTON.2015.7447112

Coded MapReduce

Songze Li, Mohammad Ali Maddah-Ali, A. Salman Avestimehr

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

95 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	964-971
Number of pages	8
ISBN (Electronic)	9781509018239
DOIs	https://doi.org/10.1109/ALLERTON.2015.7447112
State	Published - Apr 4 2016
Externally published	Yes
Event	53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015 - Monticello, United States Duration: Sep 29 2015 → Oct 2 2015

Publication series

Name	2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015

Other

Other	53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
Country/Territory	United States
City	Monticello
Period	9/29/15 → 10/2/15

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

Publisher link

10.1109/ALLERTON.2015.7447112

Find It

Find It at U of M Libraries

Cite this

Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2016). Coded MapReduce. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015 (pp. 964-971). Article 7447112 (2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2015.7447112

Coded MapReduce. / Li, Songze; Maddah-Ali, Mohammad Ali; Avestimehr, A. Salman.
2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015. Institute of Electrical and Electronics Engineers Inc., 2016. p. 964-971 7447112 (2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Li, S, Maddah-Ali, MA & Avestimehr, AS 2016, Coded MapReduce. in 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015., 7447112, 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015, Institute of Electrical and Electronics Engineers Inc., pp. 964-971, 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015, Monticello, United States, 9/29/15. https://doi.org/10.1109/ALLERTON.2015.7447112

@inproceedings{ff15de89d7374f26b0cd70ddf869c373,

title = "Coded MapReduce",

abstract = "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.",

author = "Songze Li and Maddah-Ali, {Mohammad Ali} and Avestimehr, {A. Salman}",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015 ; Conference date: 29-09-2015 Through 02-10-2015",

year = "2016",

month = apr,

day = "4",

doi = "10.1109/ALLERTON.2015.7447112",

language = "English (US)",

series = "2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "964--971",

booktitle = "2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015",

}

TY - GEN

T1 - Coded MapReduce

AU - Li, Songze

AU - Maddah-Ali, Mohammad Ali

AU - Avestimehr, A. Salman

PY - 2016/4/4

Y1 - 2016/4/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84969802749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969802749&partnerID=8YFLogxK

U2 - 10.1109/ALLERTON.2015.7447112

DO - 10.1109/ALLERTON.2015.7447112

M3 - Conference contribution

AN - SCOPUS:84969802749

T3 - 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015

SP - 964

EP - 971

BT - 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015

Y2 - 29 September 2015 through 2 October 2015

ER -

Coded MapReduce

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this