Embarassingly parallel decompositions of functions

A basic primitive of functional programming, the map function, is embarrassingly parallel. This means that map can be broken up into independent computations requiring no communication or synchronization between them except for a join operation at the end. It would be nice if we could describe embarrassing parallelism in the most general sense using category-theoretic universal properties.

To do this we will use the topos $Sets^{\to}$. It will be shown that products in this category describe embarrassingly parallel computations. If $X^n$ is the set of $n$-tuples of elements of $X$, then the map function with argument $f$ is equivalent to the product function $f^n$ of $f$ with itself $n$ times. We will describe how arbitrary functions in $Sets^{\to}$ can be given product decompositions, even when they do not use representations by sequences so that they can be treated as embarrassingly parallel functions.

Background on the algebraic theory of information:
The algebraic theory of information, introduced by Hartmanis and Stearns requires that we model information using partitions. In modern categorical treatments, partitions are equivalence classes of epimorphisms in the topos $Sets$. As every topos, including $Sets$, has epi-mono factorizations, every function in $Sets$ has an epi-component which is its partition or kernel.

Definition. let $f$ be a function then $f$ defines a partition called $ker(f)$ which describes equality with respect to $f$: $$(a,b) \in ker(f) \Leftrightarrow f(a) = f(b)$$ Example 1. let $\Omega : \{0,\frac{1}{2},1\} \to \{0,1\}$ be the object of truth values in $Sets^{\to}$ then its kernel is the equivalence relation defined by the partition $\{\{0\},\{\frac{1}{2},1\}\}$

Example 2. let $abs : \mathbb{R} \to \mathbb{R}$ be the absolute value function. Then $(-1,1) \in ker(abs)$ because $-1$ and $1$ have the same absolute value.

Background on products in Sets:
Definition. let $S_1,S_2,...S_n$ be a family of sets in the topos $Sets$. Then a universal product cone is a family of epimorphisms $f_i$ from an object $X$ to each $S_i$. By the kernel construction it follows that each $f_i$ has a corresponding partition $ker(f_i)$. These partitions have the following property: $$\forall F \in \prod_{i \in I} P_i: |\bigcap_{i \in I} F_i| = 1$$ Which equivalently states that each selection of equivalence classes for each partition has a single common intersection. To demonstrate the use of this formalism we have provided a set of examples:

Example 1. {{0,1},{2,3}} and {{0,2},{1,3}} form a product decomposition because all pairs of equivalence classes between them have singular intersection:

	0,2	1,3
0,1	0	1
2,3	2	3

Example 2. {{0,1,2},{3,4,5},{6,7,8}} and {{0,3,6},{1,4,7},{2,5,8}} form a product decomposition because all pairs of equivalence classes between them have singular intersection:

	0,3,6	1,4,7	2,5,8
0,1,2	0	1	2
3,4,5	3	4	5
6,7,8	6	7	8

Example 3. the following three equivalence classes form a product decomposition because all triples of equivalence classes chosen between the three of them have singular intersection: $$\{\{0,1,2,3\}, \{4,5,6,7\} \}$$ $$\{\{0,2,4,6\}, \{1,3,5,7\} \}$$ $$\{\{0,1,4,5\}, \{2,3,6,7\} \}$$ This can be confirmed by examining all the triples of equivalence classes of these three partitions manually to determine that they have singular intersection: $$\{0,1,2,3\} \cap \{0,2,4,6\} \cap \{0,1,4,5\} = \{0\}$$ $$\{0,1,2,3\} \cap \{0,2,4,6\} \cap \{2,3,6,7\} = \{2\}$$ $$\{0,1,2,3\} \cap \{1,3,5,7\} \cap \{0,1,4,5\} = \{1\}$$ $$\{0,1,2,3\} \cap \{1,3,5,7\} \cap \{2,3,6,7\} = \{3\}$$ $$\{4,5,6,7\} \cap \{0,2,4,6\} \cap \{0,1,4,5\} = \{4\}$$ $$\{4,5,6,7\} \cap \{0,2,4,6\} \cap \{2,3,6,7\} = \{6\}$$ $$\{4,5,6,7\} \cap \{1,3,5,7\} \cap \{0,1,4,5\} = \{5\}$$ $$\{4,5,6,7\} \cap \{1,3,5,7\} \cap \{2,3,6,7\} = \{7\}$$ Each of these eight triples are families of sets in the product $\prod_{i \in I} P_i$ that have singular intersection.

Product functions:
Definition. let $f_i: A_i \to B_i$ be a family of functions then their product in $Sets^{\to}$ is the function: $$\prod_{i \in I} f_i : \prod_{i \in I} A_i \to \prod_{i \in I} B_i$$ That is defined by applying the function $f_i$ to the value at index $i$ of a sequence in $\prod_{i \in I} A_i$: $$\prod_{i \in I} f_i(a_1,...a_n) = (f_1(a_1),...,f_n(a_n))$$ Example 1. let $f: X \to Y$ be a function then $f^n: X^n \to Y^n$ is the function that applies the higher-order map function to sequences of size $n$ using the function $f$.

Example 2. let $inc: \mathbb{R} \to \mathbb{R}$ be the function $inc(x) = x+1$ and let $double : \mathbb{R} \to \mathbb{R}$ be the function $double(x) = 2*x$. Then the function $inc \times double : \mathbb{R}^2 \to \mathbb{R}^2$ has $f(x,y) = (x+1, 2*y)$.

The critical characteristic of product functions is that they are embarrassingly parallel. Given a product function $f \times g$, the results of the functions $f$ and $g$ can be computed entirely separately from one another. Then all we need to do is combine the results of these separately computed values at the end to get a final result.

Category theory teaches us that we can treat products using universal properties instead of by reference to their common representations. The product of sets is not necessarily a set of ordered pairs but rather a universal limiting cone, and that is one of its representations. To move beyond issues of representation, we will also have to consider universal cones in $Sets^{\to}$.

Embarassingly parallel decompositions:
Proposition. let $f: A \to B$ be a function in $Sets^{\to}$. Then a decomposition of $f$ into separate information flows is a family $(P_1,Q_1), (P_2,Q_2), ... (P_n,Q_n)$ of information flows such that the source partitions $P_1, P_2, ... P_n$ form a product decomposition of $A$ and the target partitions $Q_1, Q_2, ... Q_n$ form a product decomposition of $B$.

Example 1. let $f(a,b) = (a+1,b+1)$ then ((0,0), (1,1)) form a family of flow relations where (0,1) and (0,1) are both product decompositions. These information flows produce a universal limiting cone in $Sets^{\to}$: Example 2. let $f(a,b) = (b,a)$ be the transposition function then $((0,1),(1,0))$ forms a family of flow relation where (0,1) and (1,0) are both product decompositions. These information flows produce a universal limiting cone in $Sets^{\to}$: We see now that to reconstruct a product function from a family of independent information flows, you only need to take the product of all its quotients. This demonstrates how the theory of information flows in the topos of functions $Sets^{\to}$ can be used to create embarassingly parallel decompositions.

References:
[1] Hartmanis, J., & Stearns, R. E. (1966). Algebraic structure theory of sequential machines.

[2] Bernier, J. (2023). Toposic structure theory of computations.

[3] Goldblatt, R. (2014). Topoi the categorial analysis of logic. Elsevier Science.