Parallel prefix scan and MapReduce
MapReduce paper begins its discussion of related work as follows:
Many systems have provided restricted programmingHas anyone implemented parallel prefix scan as an extension to MapReduce or a similar framework such as Hadoop, and did it prove useful?
models and used the restrictions to parallelize the computation
automatically. For example, an associative function
can be computed over all prefixes of an N element
array in log N time on N processors using parallel prefix