Trace monoid is an algebraic structure capturing concurrent computation—sequences of actions where swapping independent actions (those with no shared data) doesn't change the result. It's a partial order of instructions formalized as an equivalence class under commutativity of independent pairs, the algebraic foundation for analyzing concurrent program semantics.
// Two independent instruction chains can commute: // mov eax, 1 (a: write eax) // mov ebx, 2 (b: write ebx) — independent of (a) // add ecx, eax (c: read eax written by a) // add edx, ebx (d: read ebx written by b) — independent of (c) // Trace: {abcd, bacd, abdc, badc} all have same observable result