Difference between Strict Consistency and Sequential Consistency

Question

I understand strict and sequential consistency independently fairly well.

Strict C basically enforces the actual order in which the instructions ran on the global clock.

Sequential Consistency basically enforces the order only on one processor.

I'm having trouble putting together some literature though. http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html describes sequential consistency as allowing for memory 'lag'. It may take time for a write to propagate across all processors. But when it does, it reaches all of them at once which is fine. Thus, the following is valid under Sequential Consistency

P1:  W(x)1
-----------------------
P2:        R(x)0 R(x)1

What concerns me now is the following processes, which is something like Dekker's algorithm.

P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0

This should surely NOT be possible under Sequential consistency ( http://portal.acm.org/citation.cfm?id=1787234.1787255 pg 2). There is no total order that can give this result.

But it makes sense from the idea that sequential consistency allows writes to propagate slowly and one thread may not have any idea as to what other processors are up to.

What am I missing here?

Answer 1

You are not missing anything :)

Dekker's algorithm will not be sequentially consistent on distributed shared memory hierarchy based multiprocessor but it is very much possible as the memory updates propagate not in step with local memory (cache) update but asynchronously through Cache Coherence protocols like MESI (Weaker memory model).

On a uni-processor on which Dekker's algorithm this is not the case and it will be strictly consistent.

Answer 2

You already have the correct answer. The second execution is not sequentially consistent because "there is no total order that can give this result".

I guess your confusion comes from this idea:

the idea that sequential consistency allows writes to propagate slowly and one thread may not have any idea as to what other processors are up to.

This is correct. The propagation can be slow. Sequential consistency allows one thread not being aware of what other processes are up to (for whatever programs). However, sequential consistency does not allow every thread not being aware of what other processes are up to (for some programs, including the Dekker's algorithm).

The above phrase "for some programs" comes from this consideration: even under sequential consistency, if the threads do not use shared memory, no thread is aware of another thread's behavior.

Answer 3

This paper might also help in understanding, as its title suggests about the difference between the two consistencies you mention. (However, it is in large parts about the implementation of SeqCon and StrictCon shared objects in message-passing, which is one way to think about the lag you mentioned.)

To answer your specific question: Sequential consistency demands that all events happen in some sequential order and that what happens on one process is always consistent with time.

So the reason why

P1:  W1(x,1)  R2(y)0
-------------------
P2:  W2(y,1)  R2(x)0

is not possible, is that there has to be some global sequence, e.g. W1(x,1) R1(y)0 W2(y,1) R2(x)?. In this sequence the last read can clearly not return 0. This sequence does not have to be consistent with real-time though. It is entirely possible (sequential consistency) that in real-time the sequence of events was W1(x,1) W2(y,1) R1(y)0 R2(x)1. This sequence is illegal for strict consistency (as R1(y) did not return the value of the previous write).

Answer 4

But it makes sense from the idea that sequential consistency allows writes to propagate slowly and one thread may not have any idea as to what other processors are up to.

This is not the correct understanding of sequential consistency.

An execution is sequentially consistent if its output could have been produced by a strictly consistent execution. What your source was saying is that what actually happens in the execution doesn't matter, only the output matters. What this means is that as long as the output of an execution could have been produced by a strictly consistent execution, then the execution is sequentially consistent even if it does impossible things like reading from the future.

Therefore this execution:

P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0

Is not sequentially consistent, because it could not have been produced by a strictly consistent execution.

For an execution to be sequentially consistent, only the output matters. The actual ordering of reads and writes in the execution doesn't matter, the only thing that matters is that the output of the execution could have been produced by a strictly consistent execution of the same program.