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

<p>I guess your confusion comes from this idea:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<p>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.</p>

CC BY-SA 3.0
2011-04-08T04:23:55.663Z
2011-04-08T04:23:55.663Z
yhirai
<p><a href="http://portal.acm.org/citation.cfm?id=176576" rel="nofollow">This</a> 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.)</p>

<p>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. </p>

<p>So the reason why </p>

<pre><code>P1:  W1(x,1)  R2(y)0
-------------------
P2:  W2(y,1)  R2(x)0
</code></pre>

<p>is not possible, is that there has to be some global sequence, e.g. <code>W1(x,1) R1(y)0 W2(y,1) R2(x)?</code>. 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 <code>W1(x,1) W2(y,1) R1(y)0 R2(x)1</code>. This sequence is illegal for strict consistency (as R1(y) did not return the value of the previous write). </p>

CC BY-SA 3.0
2015-01-03T22:14:35.407Z
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
CC BY-SA 3.0
2015-01-20T21:11:21.597Z
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.
CC BY-SA 3.0
2015-01-20T21:12:34.060Z
As to what you mean exactly by "execution order is arranged to happen", I'm not sure I understand.
Martin B.
CC BY-SA 3.0
2011-04-08T08:39:11.483Z
2011-04-08T08:39:11.483Z
Martin B.
<blockquote>
<p>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.</p>
</blockquote>
<p>This is not the correct understanding of sequential consistency.</p>
<p>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 <strong>could have been produced by a strictly consistent execution</strong>, then  the execution is sequentially consistent <strong>even if it does impossible things like reading from the future</strong>.</p>
<p>Therefore this execution:</p>
<pre><code>P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0
</code></pre>
<p>Is not sequentially consistent, because it could not have been produced by a strictly consistent execution.</p>
<p>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.</p>

CC BY-SA 4.0
2024-01-20T09:23:51.970Z
2024-01-20T13:09:24.360Z
2024-01-20T13:09:24.360Z
1f604
<p>You are not missing anything :)</p>

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

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

CC BY-SA 3.0
2011-04-08T08:16:09.817Z
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
CC BY-SA 3.0
2011-04-08T09:07:37.137Z
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
CC BY-SA 3.0
2011-04-08T05:15:31.573Z
2011-04-08T05:15:31.573Z
Sai Venkat
<p>I understand strict and sequential consistency independently fairly well.</p>

<p>Strict C basically enforces the actual order in which the instructions ran on the global clock.</p>

<p>Sequential Consistency basically enforces the order only on one processor.</p>

<p>I'm having trouble putting together some literature though.
<a href="http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html">http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html</a> 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</p>

<pre><code>P1:  W(x)1
-----------------------
P2:        R(x)0 R(x)1
</code></pre>

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

<pre><code>P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0
</code></pre>

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

<p>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.</p>

<p>What am I missing here?</p>

CC BY-SA 2.5
2011-04-07T22:12:59.233Z
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
CC BY-SA 2.5
2011-04-07T23:03:45.933Z
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
CC BY-SA 3.0
2011-04-08T10:19:42.503Z
Thanks for all the answers. I also read about causal consistency and understood that what I was thinking about was exactly that.
jetru
<pl.programming-languages><dc.parallel-comp><concurrency>
Difference between Strict Consistency and Sequential Consistency
jetru
# Difference between Strict Consistency and Sequential Consistency

(Asked by: username_0 on 2011-04-07)

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?

**Tags:** pl.programming-languages, dc.parallel-comp, concurrency
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_0**: Thanks for all the answers. I also read about causal consistency and understood that what I was thinking about was exactly that.  

---

## 4 answers

### Answer by username_6 on 2011-04-08. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_6**: 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.  

---

### Answer by username_2 on 2011-04-08. Score: 4

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 by username_3 on 2011-04-08. Score: 4

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

> **Comments:**
> **username_4**: 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?  
> **username_3**: 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).  
> **username_3**: As to what you mean exactly by "execution order is arranged to happen", I'm not sure I understand.  

---

### Answer by username_5 on 2024-01-20. Score: 0

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.


---

