Monoids and Differential Dataflow

We can arbitrarily add to and remove from these collections, and differential dataflow will spring back into action and report the resulting changes to the output set, as if we had re-run the computation from scratch on the new inputs. Let’s dress up our example a bit by adding “lengths” to each edge, and rather than just checking whether a graph node is reachable from a start node, we would like to know the length of the shortest path to each reachable node. We can implement each of the graph algorithms above by maintaining the actual collections of node state as iterations unfold, which is enough for differential dataflow to determine in what ways they might change as iterations and rounds of input unfold.

Source: github.com