2014 · 42 citations · 10 references
ComputingComputer EngineeringComputer ScienceAlgorithmsDistributed SystemsParallel ComputingData ParallelismData-flow AnalysisDistributed ComputingFunctional ProgrammingNoncommutative AlgebraReduction OperationsEmpirical EvaluationMapreduceMapreduce AlgorithmsReduce
The simplicity of MapReduce introduces unique subtleties that cause hard-to-detect bugs; in particular, the unfixed order of reduce function input is a source of nondeterminism that is harmful if the reduce function is not commutative and sensitive to input order. Our extensive study of production MapReduce programs reveals interesting findings on commutativity, nondeterminism, and correctness. Although non-commutative reduce functions lead to five bugs in our sample of well-tested production programs, we surprisingly have found that many non-commutative reduce functions are mostly harmless due to, for example, implicit data properties. These findings are instrumental in advancing our understanding of MapReduce program correctness.
10
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Christopher Olston, Benjamin Reed, Utkarsh Srivastava et al. · 2008 · 1.7K citations
Ashish Thusoo, Joydeep Sen Sarma, Namit Jain et al. · Proceedings of the VLDB Endowment · 2009 · 1.5K citations
An Analysis of Traces from a Production MapReduce Cluster
Soila Kavulya, Jiaqi Tan, Rajeev Gandhi et al. · 2010 · 319 citations