@article {15301,
	title = {The Curse of Zipf and Limits to Parallelization: A Look at the Stragglers Problem in MapReduce},
	journal = {Proceedings of LSDS-IR workshop},
	year = {2009},
	month = {2009///},
	pages = {57 - 62},
	abstract = {This paper explores the problem of {\textquotedblleft}stragglers{\textquotedblright} in Map-Reduce: a common phenomenon where a small number of
mappers or reducers takes significantly longer than the oth-
ers to complete. The effects of these stragglers include un-
necessarily long wall-clock running times and sub-optimal
cluster utilization. In many cases, this problem cannot sim-
ply be attributed to hardware idiosyncrasies, but is rather
caused by the Zipfian distribution of input or intermedi-
ate data. I present a simple theoretical model that shows
how such distributions impose a fundamental limit on the
amount of parallelism that can be extracted from a large
class of algorithms where all occurrences of the same ele-
ment must be processed together. A case study in parallel
ad hoc query evaluation highlights the severity of the strag-
glers problem. Fortunately, a simple modification of the in-
put data cuts end-to-end running time in half. This example
illustrates some of the issues associated with designing effi-
cient MapReduce algorithms for real-world datasets.
},
	author = {Jimmy Lin}
}
