Stive (9) [Avatar] Offline
#1
Hello,

Section 5.3.2 :
In MapReduce, any form of reduction performed in parallel can offer different results than a
serial one if the operation is not both commutative and associative.

As far as I understood, the Reduce part needs associative functions (monoids) only.
Only Combiners need commutative functions/monoids.


Another sentence connected to that, in 5.2.3 :
This is because both operators + (plus) and < (less then) used to update and to find the closest centroid have the special properties of associativity and commutativity

< is not a monoid, since it's not a binary operation (signature : int -> int -> bool : integers not closed under < ). Therefore, it's not associative nor commutative.

Another inexact sentence :
In the k-means example, the function UpdateCentroids satisfies these laws because both of the operations used in the algorithm are monoidal operations—a scary word that hides a simple concept. These operations are addition and comparison (< less than).

Riccardo Terrell (16) [Avatar] Offline
#2
Unfortunately this is a transcript error indeed. Good catch!
you are absolutely right

As far as I understood, the Reduce part needs associative functions (monoids) only.
Only Combiners need commutative functions/monoids.


This correction is part of the fixes and re-edits that will be applied in the next push.