8

In the context of correctness of concurrent programs, Sequential consistency is stronger condition than quiescent consistency according to The art of multiprocessor programming by Maurice Herlihy and Nir Shavit(chapter 3) Authors also mention in 3.4.1 that there are sequentially consistent executions that are not quiescently consistent. I don't understand how. Could somebody throw a light or provide sample execution ?

Trojosh
  • 565
  • 1
  • 5
  • 15

1 Answers1

11

Consider a queue (FIFO) to which you enqueue and dequeue elements.

From this dissertation about concurrency, I read (p.20):

An example of a scenario that is allowed in the sequential consistency model and disallowed in the quiescent consistency model is shown in Figure 2.1. Two processes share a concurrent queue data structure. The first process enqueues x. At some non-overlapping subsequent interval, a second process enqueues y. Finally the second process performs a dequeue and receives y. This example is sequentially consistent but is not quiescently consistent, assuming that the time between enqueue operations falls outside the quiescence interval.

Figure 2.1:

T1:  --- enq(x) ---------------------------
T2:  ------------- enq(y) ---- deq():y ----

This history is permitted by sequential consistency, can be either permitted or forbidden by quiescent consistency, and is forbidden by linearizable consistency.

If you assume that between the two enqueue the queue was quiescent, then T2 should see the changes from T1, and the dequeue should return x. If you assume there was no quiescent interval between the two enqueues, then two enqueues can be reorderd as you wish, and deq():y is consistent.

Community
  • 1
  • 1
ewernli
  • 38,045
  • 5
  • 92
  • 123
  • Can the following execution be an example of "Quiescently consistent but not sequentially consistent"? T1:--enq(x)---------enq(y)------------________________________________________________ T2:-------deq(y)--------------|----deq(x)-_______________________________________________ This execution is clearly not sequentially consistent. However, if we conveniently take quiescent interval at **|** then, we could reorder two enq()s of T1 and it will be quiescently consistent. @ewernli, Do you think this explanation makes sense ? – Trojosh Oct 07 '13 at 22:11
  • I think so, based on my understanding of quiescence consistency. But that's a novel form of consistency to me as well, I learned it yesterday :) – ewernli Oct 08 '13 at 06:37
  • @ewernli is the reason this is considered sequential consistency that enq(y) deq():y enq(x) is a possible sequential execution sequence? I.E it is still valid in program order. – William Mar 21 '16 at 20:39
  • @william - sequential consistency just requires that in the execution, the operations issued by each thread must be in program order - their interleaving is not controlled. Therefore, the example you provide is indeed a valid sequentially consistent execution. – Ram Rajamony Jan 30 '17 at 03:57
  • @ewernli - thank you for posting the example from Spiegel's thesis (and thank you to him as well!). I had to go back to my Herlihy and Shavit book and re-read quiescent consistency. The key is that each quiescence period orders the operations that happened before the period from those that happen after. – Ram Rajamony Jan 30 '17 at 03:59