In computer science, a
trace is a set of strings, wherein certain letters in the string are allowed to
commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certain reshufflings to take place. Traces were introduced by Cartier and Foata in 1969 to give a combinatorial proof of
MacMahon's Master theorem. Traces are used in theories of
concurrent computation, where commuting letters stand for portions of a job that can execute independently of one another, while non-commuting letters stand for locks,
synchronization points or
thread joins.