MapReduce: From Elementary Circuits to Cloud

We regard the MapReduce mechanism as a unifying principle in the domain of computer science. Going back to the roots of AI and circuits, we show that the MapReduce mechanism is consistent with the basic mechanisms acting at all the levels, from circuits to Hadoop. At the circuit level, the elementary circuit is the smallest and simplest MapReduce circuit—the elementary multiplexer. On the structural and informational chain, starting from circuits and up to Big Data processing, we have the same behavioral pattern: the MapReduce basic rule. For a unified parallel computing perspective, we propose a novel starting point: Kleene’s partial recursive functions model. In this model, the composition rule is a true MapReduce mechanism. The functional forms, in the functional programming paradigm defined by Backus, are also MapReduce type actions. We propose an abstract model for parallel engines which embodies various forms of MapReduce. These engines are represented as a hierarchy of recursive MapReduce modules. Finally, we claim that the MapReduce paradigm is ubiquitous, at all computational levels.