MapReduce¶
Dean, J., & Ghemawat, S. (2004). MapReduce: Simplified Data Processing on Large Clusters. 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI '04), 137-150.
Retired. This is not a bibliographic entry. Our extractor captured an inline prose definition from an article and stored it as a work. The concept is real; this registry record is a parsing defect. This entry is kept so the citations that pointed at it still resolve, and so the correction is visible rather than silent.
Cited by¶
6 citations across 6 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Commutativity
- commutative algebra (the algebraic theory of commutative rings, the foundation of classical algebraic geometry); representation theory (decomposition of group actions often differs between commutative and non-commutative groups); commutative diagrams in category theory. Computer science: Parallel computation (commutative reduce operations enable arbitrary-order parallelization — MapReduce's reduce step typically requires commutativity and associativity, a class of order-independent algorithms catalogued in Knuth (1973) The Art of Computer Programming)
This sourceStates that when the Reduce operator is commutative and associative a Combiner optimization applies, so partial reductions can be applied in any order — directly supports the claim that MapReduce's reduce step typically requires commutativity and associativity. (Re-sourced from Knuth 1973, which does not catalog a class of commutativity-exploiting order-independent algorithms.)
- commutative algebra (the algebraic theory of commutative rings, the foundation of classical algebraic geometry); representation theory (decomposition of group actions often differs between commutative and non-commutative groups); commutative diagrams in category theory. Computer science: Parallel computation (commutative reduce operations enable arbitrary-order parallelization — MapReduce's reduce step typically requires commutativity and associativity, a class of order-independent algorithms catalogued in Knuth (1973) The Art of Computer Programming)
- Search and Retrieval
Domain-specific¶
- Bird–Meertens Formalism
- A list-homomorphism equation can expose independent mapping and associative combination, but it does not specify a distributed system's data partitioning, inter-machine communication or fault handling.
This sourceOriginal conference full text inspected.
- A list-homomorphism equation can expose independent mapping and associative combination, but it does not specify a distributed system's data partitioning, inter-machine communication or fault handling.
- Fallacy of Zero Transport Cost
- Rather than pulling data blocks across the network to wherever compute is free, the job scheduler places each map task, where possible, on the very node (or rack) that already holds the input block on its local disk
This sourceThe original MapReduce locality rule, which schedules a map task on a machine holding a replica of its input or, failing that, on one on the same network switch. The MapReduce design premise that network bandwidth is a relatively scarce cluster resource, conserved by reading input from local disks.
Supported in partVerified against the source
- Rather than pulling data blocks across the network to wherever compute is free, the job scheduler places each map task, where possible, on the very node (or rack) that already holds the input block on its local disk
Mechanisms¶
- Map–Combine–Reduce Pipeline
- Its strength is throughput at scale: the combiner
This sourcePresents MapReduce as scalable processing across large clusters and explains that associative, commutative combining permits correct local aggregation before reduction.
- Its strength is throughput at scale: the combiner
- Map-Reduce Reduction
- Its strength is near-linear scaling with built-in fault tolerance: because the units are independent, work spreads across a cluster and a lost unit is simply recomputed.
This sourceDescribes MapReduce’s automatic cluster parallelization, task partitioning, and fault tolerance through rescheduling or re-execution after worker failures.
- Its strength is near-linear scaling with built-in fault tolerance: because the units are independent, work spreads across a cluster and a lost unit is simply recomputed.
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Read against the text for 1 of 6 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 4 other ways.
- https://www.usenix.org/conference/osdi-04/mapreduce-simplified-data-processing-large-clusters ×2
- https://www.usenix.org/legacy/event/osdi04/tech/full_papers/dean/dean.pdf ×1
- https://www.usenix.org/legacy/event/osdi04/tech/full_papers/dean/dean_html/ ×1
- https://www.usenix.org/legacy/events/osdi04/tech/dean.html ×1
Registry ID ref:85d92bb6bb54 · see in the full table