The Commutativity Problem of MapReduce Programs
A112, Bozetechova 2, Brno 12.4.2018
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.
SpeakersChen Yu-Fang, Academia Sinica