Thomas Jahn, Complexity and Algorithms in Map-Reduce Models
Complexity and Algorithms in Map-Reduce Models
Map Reduce is a programming paradigm used at Google to easily process a massive set of data. Karloff et.al. and Goodrich et.al. introduced models describing Map Reduce from a theoretical point of view. Karloff et.al. defined the complexity class DMRC. We discuss the models, the class DMRC and some weaker definitions of it and their relations to P, NC as well as their subclasses LIN, NC0 and NC1. Based on ideas by Goodrich et.al. we also introduce new complexity classes of problems solvable by Map Reduce algorithms.