A trace monoid (also called a free partially commutative monoid, or a Mazurkiewicz trace monoid after Antoni Mazurkiewicz who introduced them in 1977) is an algebraic structure that captures the notion of concurrent computation. The idea is simple: if two actions in a program do not share any data, the order in which you execute them should not matter. A trace monoid makes this precise by taking the set of all instruction sequences and declaring two sequences equivalent if one can be obtained from the other by repeatedly swapping adjacent independent actions.
A monoid is a triple $(S, \cdot, \varepsilon)$ where $S$ is a set, $\cdot$ is a binary operation on $S$, and $\varepsilon \in S$ is an identity element, satisfying three axioms:
Strings under concatenation form the simplest example: $(\Sigma^*, \cdot, \varepsilon)$ where $\Sigma^*$ is the set of all finite strings over alphabet $\Sigma$, $\cdot$ is concatenation, and $\varepsilon$ is the empty string. This is the free monoid on $\Sigma$.
To build a trace monoid you start with a dependence alphabet $(\Sigma, D)$, where $D \subseteq \Sigma \times \Sigma$ is a reflexive and symmetric relation — the dependence relation. Its complement $I = (\Sigma \times \Sigma) \setminus D$ is the independence relation: $(a, b) \in I$ means $a$ and $b$ do not interfere and can be executed in either order.
Define a congruence on $\Sigma^*$: two strings are equivalent if one can be transformed into the other by swapping adjacent letters $ab \to ba$ wherever $(a, b) \in I$. The trace monoid $\mathbb{M}(\Sigma, I)$ is the quotient:
$$\mathbb{M}(\Sigma, I) = \Sigma^* / \sim_I$$
Each element of $\mathbb{M}(\Sigma, I)$ is an equivalence class $[w]$, called a trace.
The three monoid axioms are satisfied:
What distinguishes the trace monoid from the free monoid is that it is not free: the generators do not all commute (only independent pairs do), and it is not a group (traces have no inverses). It sits between the free monoid (no commutativity) and the free commutative monoid (everything commutes).
Consider four x86 instructions:
; description: two independent load-and-use chains; eax/ecx chain and ebx/edx chain mov eax, 1 ; (a) writes eax mov ebx, 2 ; (b) writes ebx add ecx, eax ; (c) reads eax, writes ecx add edx, ebx ; (d) reads ebx, writes edx
Two instructions are dependent if one writes a register that the other reads or writes. The dependence pairs here are $(a, c)$ (instruction $c$ reads eax which $a$ writes) and $(b, d)$ (instruction $d$ reads ebx which $b$ writes). Everything else is independent:
$$I = \{(a,b),\,(b,a),\,(a,d),\,(d,a),\,(b,c),\,(c,b),\,(c,d),\,(d,c)\}$$
The sequential program is the string $abcd$. Since $(a, b) \in I$, swapping $a$ and $b$ produces an equivalent string. Since $(c, d) \in I$, swapping $c$ and $d$ also produces an equivalent string. The full equivalence class — the trace $[abcd]$ — contains four sequences:
$$[abcd] = \{abcd,\; bacd,\; abdc,\; badc\}$$
Two of those orderings written out explicitly:
; trace member 1: original order mov eax, 1 mov ebx, 2 add ecx, eax add edx, ebx
; trace member 2: swap the two independent loads first mov ebx, 2 mov eax, 1 add ecx, eax add edx, ebx
Both produce identical register state afterwards. A compiler or out-of-order CPU is free to choose any member of the trace; the observable result is the same. The trace $[abcd]$ is not just a sequence but a partial order: $a$ must precede $c$, and $b$ must precede $d$, but there is no ordering constraint between the two chains.
The connection to concurrency is direct: if $a, b, c, d$ are actions of a concurrent program, any serialisation that respects the partial order encoded in the trace is a valid execution. Trace monoids are the algebraic foundation for Mazurkiewicz trace theory, which gives a precise language for talking about the semantics of concurrent systems without tying behaviour to a specific interleaving.