Under de senaste åren har ramen MapReduce vuxit fram som en av de mest använda parallella datorplattformarna för behandling av data på terabyte- och petabyteskalor. Används dagligen på företag som Yahoo!, Google, Amazon och Facebook, och antagits på senare tid av flera universitet, möjliggör det enkel parallellisering av dataintensiva beräkningar över många maskiner. En viktig egenskap hos MapReduce som skiljer den från tidigare modeller av parallell beräkning är att den interleaves sekventiell och parallell beräkning. Vi föreslår en modell för effektiv beräkning med hjälp av MapReduce paradigm. Eftersom MapReduce är utformad för beräkningar över massiva datamängder, begränsar vår modell antalet maskiner och minnet per maskin till att i huvudsak vara sublinjära i storleken på inmatningen. Å andra sidan sätter vi mycket lösa restriktioner på beräkningskraften hos varje enskild maskin vår modell gör att varje maskin att utföra sekventiella beräkningar i tid polynom i storleken på den ursprungliga inmatningen. Vi jämför MapReduce med PRAM-modellen för beräkning. Vi visar en simuleringslemma som visar att en stor klass av PRAM-algoritmer effektivt kan simuleras via MapReduce. Styrkan i MapReduce ligger dock i det faktum att den använder både sekventiell och parallell beräkning. Vi demonstrerar hur algoritmer kan dra nytta av detta faktum för att beräkna en MST av en tät graf i endast två rundor, i motsats till  på (log(n)) rundor som behövs i standard PRAM-modellen. Vi visar hur man utvärderar en bred klass av funktioner med MapReduce-ramverket. Vi avslutar med att tillämpa detta resultat för att visa hur man beräknar några grundläggande algoritmiska problem såsom oriktad s-t-anslutning i MapReduce-ramverket.
Ett vanligt antagande i MapReduce-modellen är till exempel att antalet processorer är n δ för vissa små δ REF.
A model of computation for MapReduce
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}