Sequential Consistency

The key idea is that each thread should run its instructions in sequence.

In between threads, sequentially consistent operations occur in sequence (not at the same time).

Overall this leads to some interleaving sequence of instructions from all threads executed, where all threads observe the same sequence.

More elaboration on total orders

For between two threads it is simple if two instructions happen in sequence - but what do other threads observe?

T1:
x = 1

T2:
x = 2

T3:
print x;

Whichever order T1 and T2 execute their instructions, T3 will observe the SAME order.

This is the same case for all pairings of T1, T2 and T3. There is a total order of instructions.

So interleaving is known statically?

BUT note that this is some interleaving. We can’t know statically (i.e. just by looking at the code) how the code will interleave.

The total order is only known DURING runtime, as the program executes, from the perspective of each thread the order in which instructions interleave will be the same.