• The state of a concurrent program consists of the values of the program variables at a point in time:
• variables both explicitly declared by the programmer as well as implicit variables like the program counter or stack pointer
• each process changes the program state independently

• A process executes a sequence of statements and each statement consists of a seqeuence of one or more atomic actions, which are actions that indivisibly examine or change the program state
• e.g., uniterraptible machine instructions or microinstructions reading or writing a word to the memory
• The execution of a concurrent program results in an interleaving of the sequences of atomic actions executed by each process, and a particular execution of a concurrent program produces a history, a sequence (trace) of states: s₀ -> s₁-> ... -> s_n and the transitions are made by atomic actions that alter the state

• it is assumed that the effect of executing a set of atomic actions in parallel is equivalent to executing in some serial order (very strong and very often questioned assumption!)
• the number of possible histories is enormous (e.g., execution of n independent parallel atomic actions can be interleaved in n! ways)
• the role of synchronization is to constrain the possible histories of a concurrent program to desirable histories, e.g.,
• mutual exclusion combines atomic actions into sequence of actions called critical sections that appear to be atomic, i.e. cannot be interleaved with actions in other processes that reference the same variables
• condition synchronization delays an action until the state satisfies a Boolean condition