Why is quiescent consistency compositional, but sequential consistency is not

Question

I'm having trouble in comparing these two memory consistency models.

Essentially for sequential consistency I think of real code like this:

int x, y;

void ThreadA()
{
   x = 20; //Write
   int a = y; //Read
}

void ThreadB()
{
    y = 20;
    int b = x;
}

In a sequential consistency environment it's impossible for a or b to not be 20. That is either a = 20, b = 20 or a = 20 && b = 20.

But how does quiescent consistency fit in to this example, and why is it compositional?

Answer 1

Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you.

First, let's start with sequential consistency. A model has this property if operations appear to take effect in program order. In other words, the order in which lines of code are executed is the one specified in the source file. This prerequisite is thread-specific: operations involving different threads are unrelated by the program order. So, the property grants the following: operations issued by the same thread are executed in the same order specified by the thread source code. Operations issued by different threads can happen in any order. This prerequisite may seem obvious, but it is not always the case (compiler optimizations may change the order in which operations are issued, thus making the program order different from the source).

Your example is right, but let me give you some others. Consider this program P1 (I'll tag each line for an easy reference):

   int x = 1;

   void ThreadA()
   {
A1:    x = x * 2;
A3:    int a = x;
   }

   void ThreadB()
   {
B2:    x = 20;
   }

Is there a sequential execution in which, at the end, a = 40? Yes: B2, A1, A3.

B2 and A1 can be executed in any order (they belong to different threads). A1 is executed before A3 (program order = source code order).

Now consider this program P2:

   int y = 1;

   void ThreadA()
   {
A2:    y = 40;
   }

   void ThreadB()
   {
B1:    y = y / 2;
B3:    int b = y;
   }

Is there a sequential execution in which, at the end, b = 20? Yes: A2, B1, B3.

What about composition? Let's compose P1 and P2. We get P1∘P2:

   int x = 1;
   int y = 1;

   void ThreadA()
   {
A1:    x = x * 2;
A2:    y = 40;
A3:    int a = x;
   }

   void ThreadB()
   {
B1:    y = y / 2;
B2:    x = 20;
B3:    int b = y;
   }

If sequential consistency were compositional, then there should be an execution in which, at the end, a = 40 and b = 20. Is this the case? No. Let's give a formal proof oh why it can't be the case. I'll write "o1 → o2" to say that the operation o1 must be executed before operation o2.

In P1∘P2, due to sequential consistency, the following must holds: A1 -> A2 and B1 -> B2 (per-thread program order). In order to get a = 40 also B2 -> A1 must hold. In order to get b = 20 also A2 -> B1 must hold. Can you see the precedence chain? A1 -> A2 -> B1 -> B2 -> A1 -> ...

P1 and P2 were sequentially consistent, but their composition P1∘P2 was not. Sequential consistency is not compositional. The example you provided was not tricky enough to show this fact.

Now, let's consider quiescent consistency. It's difficult for me to explain this property without using the object-oriented paradigm. In fact, quiescent consistency can be easily understood in terms of pending method calls on objects. Nevertheless, I'll try to stick with the imperative paradigm (pending method calls become functions started but not completed, objects become variables involved in functions).

A function call is composed by an invocation and a response. A function is pending if it has been invoked by a thread but it has not returned a response yet to such thread. A period of quiescence for a variable is a time interval in which there are no pending function calls (by any thread) operating on it. A model has the quiescent consistency property if function calls operating on the same variable and separated by a period of quiescence appear to take effect in their real-time order (the one specified by source code). From the converse point of view, the definition states that operations on the same variable executed by functions called concurrently by different threads (not separated by quiescence) can happen in any order.

I've tried for many hours to design a meaningful example using only read-write operations to show you the difference between quiescent and sequential consistency, but I didn't succeed. Let me use another example involving sets. I will use a bit vector to keep track of which integers (from 0 to 4) are in the set:

   int set[5] = {0, 0, 0, 0, 0};  // 0 if i-th item is absent, 1 otherwise

   void add(int number) {
L1:    set[number] = 1;
L2:    temp foo = set[0];
   }

   void remove(int number) {
       set[number] = 0;
   }

   int contains(int number) {
       return set[number] == 1;
   }

   void ThreadA()
   {
A1:    add(1);
   }

   void ThreadB()
   {
B1:    add(2);
B2:    remove(2);
B3:    int res = contains(2);
   }

Is there a sequential execution in which, at the end, res = 1? No: due to sequential consistency B1 -> B2 and B2 -> B3, so B1 -> B3. So, remove(2) is always executed after add(2) and contains(2) will always returns 0.

Is there a quiescent execution in which, at the end, res = 1? Yes! Consider this execution:

Thread A invokes add(1) at A1.

Thread A executes L1 (but not L2). // since there is a pending call on the set, now Thread B is free to execute B2 before B1 because these calls involve the set as well

Thread B calls B2. // invocation + response

Thread B calls B1. // invocation + response

Thread A executes L2 and add(1) responds. // now there is quiescence on the set

Thread B executes B3. // invocation + response

Now res = 1.

Unfortunately, I still can't answer the latest question on why quiescent consistency is compositional: I found your question while I was looking for this exact answer indeed. If I come up with something I'll let you know.

For a good reading on the topic have a look at chapter 3.3 of the book "The Art of Multiprocessor Programming" by Herlihy and Shavit.

EDIT: I've just found a great page explaining why quiescent consistency is compositional. And this is another very good reading!

EDIT2: Fixed little error in the sequential consistency composability example.