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?

  • I think you are confusing sequential consistency and causal consistency. SC is a stronger condition than your intuitive phrasing... if I am understanding you correctly. Your second execution is CC (and PRAM C) but not SC. – Aaron Sterling Apr 7 '11 at 22:12
  • Yes perhaps. My question is specifically why is the second execution NOT sequentially consistent? If the first one is, what is the special reasoning that makes execution 2 inconsistent? – jetru Apr 7 '11 at 23:03
  • Thanks for all the answers. I also read about causal consistency and understood that what I was thinking about was exactly that. – jetru Apr 8 '11 at 10:19
up vote 8 down vote accepted

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.

  • So by considering memory updates propagation, I'm actually relaxing the memory model, hence in my imagined memory model, execution 2 is possible. In a properly sequentially consistent memory store, the writes would propagate instantly. Is this right? – jetru Apr 8 '11 at 8:16
  • 1
    Yes.. If every process looks only at its local memory execution 2 is possible. In a properly sequential consistency the writes need not propagate instantly but when other location refer or update to the location written which is normally the case. – Sai Venkat Apr 8 '11 at 9:07

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.

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).

  • Sorry about late comment, but could it be possible that W1(x,1) W2(y,1) R1(y)1 R2(x)1 happens in a sequentially consistent environment too? If the execution order is arranged to happen in this order before it happens in time? – William Jan 3 '15 at 22:14
  • The execution W1(x,1) W2(y,1) R1(y)1 R2(x)1 is sequentially consistent, even strictly consistent, if I'm not mistaken (I'm a bit tired already today). – Martin B. Jan 20 '15 at 21:11
  • As to what you mean exactly by "execution order is arranged to happen", I'm not sure I understand. – Martin B. Jan 20 '15 at 21:12

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.