The Commutativity Problem of MapReduce Programs
12 April 2018 Seminář
A112, Božetěchova 2, Brno, CZ
MapReduce is a popular programming model for data-parallel computation. In MapReduce, the reducer produces an output from a list of inputs. Due to the scheduling policy of the platform, the inputs may arrive at the reducers in a different order. The commutativity problem of reducers asks if the output of a reducer is independent of the order of its inputs. Although the problem is undecidable in general, the MapReduce programs in practice are usually used for data analytics and thus require very simple data and control flow, which allows solving some practical instances of the problem. The talk will present our current progress towards a complete solution to the commutativity problem.