Short answer, if your operations are communicative the order of your output/input doesn't matter making it much easier to schedule operations since you don't have to worry about order. This is a nice feature when parallel processing since you have to do much less synchronization.
Rock-Paper-Scissors Problem: (Add spock and lizard for bonus points ;)
Say you have a long string of RPS and want to know who is left standing. Assume the ouput is the same as the game carried out when you iteratively match up the first two elements in the list until there is only one left.
RPSSPSRSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPRPSSPRRRRSPSPSPPPRSPSPSRP
Multiplication table:
RR->R
PP->P
SS->S
RS->R
SR->R
SP->S
PS->S
RP->P
PR->P
Sit down and figure out how you can evaluate a huge RPS string in parallel.... (solution at the bottom)
Check out their test library for use cases:
https://github.com/twitter/algebird/tree/develop/src/test/scala/com/twitter/algebird
Or the code itself:
https://github.com/twitter/algebird/tree/develop/src/main/scala/com/twitter/algebird
It is a generic programming framework for data types that support the concepts of 0,1,plus, times, inverse ... The user has to write a wrapper in Scala that takes care of the memory management, and carries out the operations. Depending on which concepts the data structure implements it will fall into some abstract algebra concept: group, semigroup, monoid,... where you can use specialized algorithms specific to that generic abstract algebra concept to achieve your computational goals.
For example if you have a communicative operation, it may be faster than an associative one since you are allowed to reorder the elements; however the framework needs to know this in order to make optimizations.
IMHO a C++/Python/Java/Ruby framework based around parallel prefix would have been more useful. Also, the documentation is sort of lacking. I couldn't easily find a concise example of how to take your data structure and wrap it with all the functions it needs for the framework.
Parallel RPS solution.
Think of it as a three state finite state machine R, P, S; with transitions R, P, S.
First encode R->0, P-> 1, S ->2.
Rock transform {RR->R, PR -> P, SR -> R} | {00->0, 10->1, 20->0} | {0,1,0}
Paper transform {RP->P, PP->P, SP -> S} | {1,1,2}
Scissors transform {RS->R, PS->S, SS->S } | {0,2,2}
Now apply a parallel prefix on the transformations {0,1,0}, {1,1,2}, and {0,2,2} under transformation composition; just like permutation composition/multiplication where you do f(g(x)).
How would algebird help you with that? Eh.... not sure.
Let $h$ be a random minhash function (note --- I'm not entirely sure what a minhash function is, but I don't believe this actually matters for the explaination).
We have that:
$$d(x,y) = \mathbb{P}[h(x)!=h(y)]$$
We want to show that:
$$\mathbb{P}[h(x) != h(y)] \leq \mathbb{P}[h(x) != h(z)] + \mathbb{P}[h(z) != h(y)]$$
When they say "When $h(x)!= h(y)$", this is the same as conditioning each probability on the fact that $h(x)!=h(y)$, so we get:
$$\mathbb{P}[h(x)!=h(y)\mid h(x)!=h(y)] \leq \overbrace{\mathbb{P}[h(x)!=h(z)\mid h(x)!=h(y)]}^{A} +\overbrace{\mathbb{P}[h(z)!=h(y)\mid h(x)!=h(y)]}^{B}$$
Clearly, the very left probability is $1$.
Now, if at least one of the probabilities on the right is $1$, we'll be done.
It's easy to see this will be the case.
Imagine $h(x) = h(z)$.
Then, the probability marked $A$ will be $0$, but because $h(x)!=h(y)$, we'll have that $h(z) != h(y)$ (as $h(x) = h(z)$ here), so the probability marked $B$ will always occur (so will contribute $1$), so the inequality will be satisfied.
Now, imagine $h(z) = h(y)$.
Then, reversing the above argument, $B$ will contribute $0$ and $A$ will contribute $1$, and the inequality will be satisfied.
If neither of these are true, then we have that $h(z)!=h(y)$ and $h(x)!=h(z)$, so $A$ and $B$ will both contribute $1$, and the inequality is satisfied.
So essentially, they just check all the possibilities.
One possibility they don't check is when the very left probability is $0$ (so condition all events on $h(x) = h(y)$, but we don't need to do this, as all probabilities are greater than or equal to $0$, so whatever appears on the right will satisfy the inequality.
Best Answer
This is a sentence a few lines above the particular example
This property is not satisfied, in particular, odd-numbered bins would not have any entry if $B=10$.
However, if $B$ is $11$, then we have $h(2)=2, h(4)=4, h(6)=6, h(8)=8, h(10)=10, h(12)=1$ and so on. Note that even the odd-bins would be filled uniformly. This phenomenon is due to $2$ and $11$ are coprime.