Theoretical Computer Science
pl.programming-languages dc.parallel-comp concurrency
Updated Tue, 07 Jun 2022 05:57:48 GMT

Difference between Strict Consistency and Sequential Consistency


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?




Solution

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 (2)

  • +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? — Apr 08, 2011 at 08: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. — Apr 08, 2011 at 09:07