History monoid

Histories

For every ${\displaystyle a\in \mathrm{\Sigma }}$, the tuple ${\displaystyle \pi (a)}$ is called the elementary history of a. It serves as an indicator function for the inclusion of a letter a in an alphabet ${\displaystyle {\mathrm{\Sigma }}_k}$. That is,

${\displaystyle \pi (a)=(a_1,a_2,\dots ,a_n)}$

where

${\displaystyle a_k=\{\begin{array}{l}a\text{ if }a\in {\mathrm{\Sigma }}_k\\ \epsilon \text{ otherwise }.\end{array}}$

Here, ${\displaystyle \epsilon }$ denotes the empty string. The history monoid ${\displaystyle H(A)}$ is the submonoid of the product monoid ${\displaystyle P(A)}$ generated by the elementary histories: ${\displaystyle H(A)=\{\pi (a)|a\in \mathrm{\Sigma }{\}}^{\ast }}$ (where the superscript star is the Kleene star applied with a component-wise definition of composition as given above). The elements of ${\displaystyle H(A)}$ are called global histories, and the projections of a global history are called individual histories.

Connection to computer science

The use of the word history in this context, and the connection to concurrent computing, can be understood as follows. An individual history is a record of the sequence of states of a process (or thread or machine); the alphabet ${\displaystyle {\mathrm{\Sigma }}_k}$ is the set of states of the process.

A letter that occurs in two or more alphabets serves as a synchronization primitive between the various individual histories. That is, if such a letter occurs in one individual history, it must also occur in another history, and serves to "tie" or "rendezvous" them together.

Consider, for example, ${\displaystyle {\mathrm{\Sigma }}_1=\{a,b,c\}}$ and ${\displaystyle {\mathrm{\Sigma }}_2=\{a,d,e\}}$. The union alphabet is of course ${\displaystyle \mathrm{\Sigma }=\{a,b,c,d,e\}}$. The elementary histories are ${\displaystyle (a,a)}$, ${\displaystyle (b,\epsilon )}$, ${\displaystyle (c,\epsilon )}$, ${\displaystyle (\epsilon ,d)}$ and ${\displaystyle (\epsilon ,e)}$. In this example, an individual history of the first process might be ${\displaystyle bcbcc}$ while the individual history of the second machine might be ${\displaystyle ddded}$. Both of these individual histories are represented by the global history ${\displaystyle bcbdddcced}$, since the projection of this string onto the individual alphabets yields the individual histories. In the global history, the letters ${\displaystyle b}$ and ${\displaystyle c}$ can be considered to commute with the letters ${\displaystyle d}$ and ${\displaystyle e}$, in that these can be rearranged without changing the individual histories. Such commutation is simply a statement that the first and second processes are running concurrently, and are unordered with respect to each other; they have not (yet) exchanged any messages or performed any synchronization.

The letter ${\displaystyle a}$ serves as a synchronization primitive, as its occurrence marks a spot in both the global and individual histories, that cannot be commuted across. Thus, while the letters ${\displaystyle b}$ and ${\displaystyle c}$ can be re-ordered past ${\displaystyle d}$ and ${\displaystyle e}$, they cannot be reordered past ${\displaystyle a}$. Thus, the global history ${\displaystyle bcdabe}$ and the global history ${\displaystyle bdcaeb}$ both have as individual histories ${\displaystyle bcab}$ and ${\displaystyle dae}$, indicating that the execution of ${\displaystyle d}$ may happen before or after ${\displaystyle c}$. However, the letter ${\displaystyle a}$ is synchronizing, so that ${\displaystyle e}$ is guaranteed to happen after ${\displaystyle c}$, even though ${\displaystyle e}$ is in a different process than ${\displaystyle c}$.

Properties

A history monoid is isomorphic to a trace monoid, and as such, is a type of semi-abelian categorical product in the category of monoids. In particular, the history monoid ${\displaystyle H({\mathrm{\Sigma }}_1,{\mathrm{\Sigma }}_2,\dots ,{\mathrm{\Sigma }}_n)}$ is isomorphic to the trace monoid ${\displaystyle \mathbb{M}(D)}$ with the dependency relation given by

${\displaystyle D=\left({\mathrm{\Sigma }}_1\times {\mathrm{\Sigma }}_1\right)\cup \left({\mathrm{\Sigma }}_2\times {\mathrm{\Sigma }}_2\right)\cup \cdots \cup \left({\mathrm{\Sigma }}_n\times {\mathrm{\Sigma }}_n\right).}$

In simple terms, this is just the formal statement of the informal discussion given above: the letters in an alphabet ${\displaystyle {\mathrm{\Sigma }}_k}$ can be commutatively re-ordered past the letters in an alphabet ${\displaystyle {\mathrm{\Sigma }}_j}$, unless they are letters that occur in both alphabets. Thus, traces are exactly global histories, and vice versa.

Conversely, given any trace monoid ${\displaystyle \mathbb{M}(D)}$, one can construct an isomorphic history monoid by taking a sequence of alphabets ${\displaystyle {\mathrm{\Sigma }}_{a,b}=\{a,b\}}$ where ${\displaystyle (a,b)}$ ranges over all pairs in ${\displaystyle D}$.