  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
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 control flow. By exploiting the
simplicity, we propose a programming language for reducers where the
commutativity problem is decidable. The main idea of the reducer language is to
separate the control and data flow of programs and disallow arithmetic
operations in the control flow. The decision procedure for the commutativity
problem is obtained through a reduction to the equivalence problem of streaming
numerical transducers (SNTs), a novel automata model over infinite alphabets
introduced in this paper. The design of SNTs is inspired by streaming
transducers (Alur and Cerny, POPL 2011). Nevertheless, the two models are
intrinsically different since the outputs of SNTs are integers while those of
streaming transducers are data words. The decidability of the equivalence of
SNTs is achieved with an involved combinatorial analysis of the evolvement of
the values of the integer variables during the runs of SNTs.
