Definition
Interleaving
Given
threads with statement sequences , an interleaving is a total order on such that The set
of all interleavings is the exhaustive space of executions under any memory model that serialises memory operations.
Examples
Two threads
Let
and . The local program orders are and . All interleavings:
For
threads with statements each, For two equal-length threads this is
; here gives . Because different runtimes, scheduling, and hardware can realise any interleaving, correctness arguments must account for all of them.