Scheduling divisible MapReduce computations

In this paper we analyze MapReduce distributed computations as a divisible load scheduling problem. The two operations of mapping and reducing can be understood as two divisible applications with precedence constraints. A divisible load model of the computation, and two load partitioning algorithms are proposed. Performance limits of MapReduce computations are investigated. To our best knowledge this is the first time that processing applications with precedence constraints have been considered on the grounds of divisible load theory.

Research highlights
► MapReduce as two divisible applications with precedence constraints.
► High complexity of reducing dominates in performance of MapReduce.
► The amount of mapper results a key parameter controlling the performance of MapReduce.
► Reducing time domination can override gains from certain optimizations.
► The influence of load unit size on performance is marginal.