Example of execution which is sequentially consistent but not quiescently consistent

Question

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 ?

Answer 1

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.