The Commutativity Problem of MapReduce Programs

A112, Božetěchova 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.



Chen Yu-Fang, Academia Sinica


Bažík Martin, FIT VUT
Hruban Milan, FIT VUT
Kotoun Michal, Bc., FIT VUT
Marko Július, FIT VUT
Zauška Ján, FIT VUT

Your IPv4 address:
Switch to IPv6 connection

DNSSEC [dnssec]